← Home
package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {
	reader := bufio.NewReader(os.Stdin)
	var n int
	fmt.Fscan(reader, &n)

	h := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Fscan(reader, &h[i])
	}

	dp := make([]int, n)
	for i := 1; i < n; i++ {
		dp[i] = n 
	}
	dp[0] = 0

	stack1 := make([]int, 0, n) 
	stack2 := make([]int, 0, n) 

	for j := 0; j < n; j++ {
		for len(stack1) > 0 {
			top := stack1[len(stack1)-1]
			if dp[top]+1 < dp[j] {
				dp[j] = dp[top] + 1
			}
			if h[top] == h[j] {
				stack1 = stack1[:len(stack1)-1]
				break
			} else if h[top] < h[j] {
				stack1 = stack1[:len(stack1)-1]
			} else {
				break
			}
		}
		stack1 = append(stack1, j)

		for len(stack2) > 0 {
			top := stack2[len(stack2)-1]
			if dp[top]+1 < dp[j] {
				dp[j] = dp[top] + 1
			}
			if h[top] == h[j] {
				stack2 = stack2[:len(stack2)-1]
				break
			} else if h[top] > h[j] {
				stack2 = stack2[:len(stack2)-1]
			} else {
				break
			}
		}
		stack2 = append(stack2, j)
	}

	fmt.Println(dp[n-1])
}