There are $n$ beautiful skyscrapers in New York, the height of the $i$-th one is $h_i$. Today some villains have set on fire first $n - 1$ of them, and now the only safety building is $n$-th skyscraper.

Let's call a jump from $i$-th skyscraper to $j$-th ($i < j$) discrete, if all skyscrapers between are strictly lower or higher than both of them. Formally, jump is discrete, if $i < j$ and one of the following conditions satisfied:   $i + 1 = j$  $\max(h_{i + 1}, \ldots, h_{j - 1}) < \min(h_i, h_j)$  $\max(h_i, h_j) < \min(h_{i + 1}, \ldots, h_{j - 1})$. 

At the moment, Vasya is staying on the first skyscraper and wants to live a little longer, so his goal is to reach $n$-th skyscraper with minimal count of discrete jumps. Help him with calcualting this number.


-----Input-----

The first line contains a single integer $n$ ($2 \le n \le 3 \cdot 10^5$) — total amount of skyscrapers.

The second line contains $n$ integers $h_1, h_2, \ldots, h_n$ ($1 \le h_i \le 10^9$) — heights of skyscrapers.


-----Output-----

Print single number $k$ — minimal amount of discrete jumps. We can show that an answer always exists.


-----Examples-----
Input
5
1 3 1 4 5

Output
3
Input
4
4 2 2 4

Output
1
Input
2
1 1

Output
1
Input
5
100 1 100 1 100

Output
2


-----Note-----

In the first testcase, Vasya can jump in the following way: $1 \rightarrow 2 \rightarrow 4 \rightarrow 5$.

In the second and third testcases, we can reach last skyscraper in one jump.

Sequence of jumps in the fourth testcase: $1 \rightarrow 3 \rightarrow 5$.

Source: codeforces | Difficulty: HARD
Tags: Dynamic programming

Graph algorithms

Data structures


Solutions:
import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush, nsmallest
from math import ceil, floor, gcd, fabs, factorial, fmod, sqrt, inf, log
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
from decimal import Decimal
mod = 10 ** 9 + 7
mod2 = 998244353

def data():
	return sys.stdin.readline().strip()

def out(var, end='\n'):
	sys.stdout.write(str(var) + end)

def outa(*var, end='\n'):
	sys.stdout.write(' '.join(map(str, var)) + end)

def l():
	return list(sp())

def sl():
	return list(ssp())

def sp():
	return map(int, data().split())

def ssp():
	return map(str, data().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(n, val) for j in range(m)]
n = int(data())
arr = l()
dp = [0] * n
(s1, s2) = ([[0, arr[0]]], [[0, -arr[0]]])
for i in range(1, n):
	temp = 10 ** 9
	while s1 and arr[i] > s1[-1][1]:
		temp = min(temp, s1.pop()[0])
	if s1:
		temp = min(temp, s1[-1][0])
		if s1[-1][1] == arr[i]:
			s1.pop()
	dp[i] = 1 + temp
	temp = 10 ** 9
	while s2 and -arr[i] > s2[-1][1]:
		temp = min(temp, s2.pop()[0])
	if s2:
		temp = min(temp, s2[-1][0])
		if s2[-1][1] == -arr[i]:
			s2.pop()
	dp[i] = min(dp[i], 1 + temp)
	s1.append([dp[i], arr[i]])
	s2.append([dp[i], -arr[i]])
out(dp[-1])


n = int(input())
arr = list(map(int, input().split()))
stackgre = [0]
stackless = [0]
dp = [0] * n
dp[0] = 0
for i in range(1, n):
	dp[i] = dp[i - 1] + 1
	while stackless and arr[stackless[-1]] >= arr[i]:
		c = arr[stackless[-1]]
		stackless.pop()
		if arr[i] < c and stackless:
			dp[i] = min(dp[stackless[-1]] + 1, dp[i])
	while stackgre and arr[stackgre[-1]] <= arr[i]:
		c = arr[stackgre[-1]]
		stackgre.pop()
		if arr[i] > c and stackgre:
			dp[i] = min(dp[stackgre[-1]] + 1, dp[i])
	stackgre.append(i)
	stackless.append(i)
print(dp[-1])


n = int(input())
h = list(map(int, input().split()))
a = [0] * n
a1 = [0]
a2 = [0]
for i in range(1, n):
	a[i] = a[i - 1] + 1
	while len(a1) and h[i] >= h[a1[-1]]:
		x = a1[-1]
		a1.pop()
		if h[i] > h[x] and len(a1):
			a[i] = min(a[i], a[a1[-1]] + 1)
	while len(a2) and h[i] <= h[a2[-1]]:
		x = a2[-1]
		a2.pop()
		if h[i] < h[x] and len(a2):
			a[i] = min(a[i], a[a2[-1]] + 1)
	a1.append(i)
	a2.append(i)
print(a[-1])


def iin():
	return int(input())

def lin():
	return list(map(int, input().split()))

def main():
	n = iin()
	a = lin()
	dp = [i for i in range(n)]
	left_less = [-1] * n
	left_greater = [-1] * n
	right_less = [-1] * n
	right_greater = [-1] * n
	stack = []
	for i in range(n):
		while stack and stack[-1][0] < a[i]:
			stack.pop()
		if stack:
			left_less[i] = stack[-1][1]
		stack.append([a[i], i])
	stack = []
	for i in range(n - 1, -1, -1):
		while stack and stack[-1][0] < a[i]:
			stack.pop()
		if stack:
			right_less[i] = stack[-1][1]
		stack.append([a[i], i])
	stack = []
	for i in range(n):
		while stack and stack[-1][0] > a[i]:
			stack.pop()
		if stack:
			left_greater[i] = stack[-1][1]
		stack.append([a[i], i])
	stack = []
	for i in range(n - 1, -1, -1):
		while stack and stack[-1][0] > a[i]:
			stack.pop()
		if stack:
			right_greater[i] = stack[-1][1]
		stack.append([a[i], i])
	points = [[] for i in range(n)]
	for i in range(n):
		if left_less[i] != -1:
			points[left_less[i]].append(i)
		if left_greater[i] != -1:
			points[left_greater[i]].append(i)
		if right_less[i] != -1:
			points[i].append(right_less[i])
		if right_greater[i] != -1:
			points[i].append(right_greater[i])
	dp[0] = 0
	for i in range(n):
		for p in points[i]:
			dp[p] = min(dp[p], dp[i] + 1)
	print(dp[n - 1])
main()


import collections

def DCJ(n, heights):
	path = [{i + 1} for i in range(n)]

	def monotonic(x):
		temp = []
		for (i, h) in enumerate(x):
			while temp and temp[-1][1] < h:
				temp.pop()
			if temp:
				path[temp[-1][0]].add(i)
			temp.append((i, h))
		temp = []
		for (i, h) in enumerate(x[::-1]):
			while temp and temp[-1][1] < h:
				temp.pop()
			if temp:
				path[n - 1 - i].add(temp[-1][0])
			temp.append((n - 1 - i, h))
	monotonic(heights)
	monotonic([-x for x in heights])
	visited = [1] + [0] * (n - 1)
	queue = collections.deque()
	queue.append((0, 1))
	while queue:
		(i, jump) = queue.popleft()
		for j in path[i]:
			if j == n - 1:
				return jump
			if not visited[j]:
				visited[j] = 1
				queue.append((j, jump + 1))
n = int(input())
heights = list(map(int, input().split(' ')))
print(DCJ(n, heights))


import sys
input = sys.stdin.readline
n = int(input())
H = list(map(int, input().split()))
EDGE = [[] for i in range(n)]
Q = []
for i in range(n):
	while Q and Q[-1][0] > H[i]:
		Q.pop()
	if Q:
		EDGE[Q[-1][1]].append(i)
		Q.append((H[i], i))
	else:
		Q.append((H[i], i))
Q = []
for i in range(n):
	while Q and Q[-1][0] < H[i]:
		Q.pop()
	if Q:
		EDGE[Q[-1][1]].append(i)
		Q.append((H[i], i))
	else:
		Q.append((H[i], i))
Q = []
for i in range(n - 1, -1, -1):
	while Q and Q[-1][0] > H[i]:
		Q.pop()
	if Q:
		EDGE[i].append(Q[-1][1])
		Q.append((H[i], i))
	else:
		Q.append((H[i], i))
Q = []
for i in range(n - 1, -1, -1):
	while Q and Q[-1][0] < H[i]:
		Q.pop()
	if Q:
		EDGE[i].append(Q[-1][1])
		Q.append((H[i], i))
	else:
		Q.append((H[i], i))
DP = [1 << 30] * n
DP[0] = 0
for i in range(n):
	for j in EDGE[i]:
		DP[j] = min(DP[j], DP[i] + 1)
print(DP[n - 1])


from __future__ import division, print_function
import bisect
import math
import heapq
import itertools
import sys
from collections import deque
from atexit import register
from collections import Counter
from functools import reduce
if sys.version_info[0] < 3:
	from io import BytesIO as stream
else:
	from io import StringIO as stream
if sys.version_info[0] < 3:

	class dict(dict):

		def items(self):
			return dict.iteritems(self)

		def keys(self):
			return dict.iterkeys(self)

		def values(self):
			return dict.itervalues(self)
	input = raw_input
	range = xrange
	filter = itertools.ifilter
	map = itertools.imap
	zip = itertools.izip

def sync_with_stdio(sync=True):
	global input, flush
	if sync:
		flush = sys.stdout.flush
	else:
		sys.stdin = stream(sys.stdin.read())
		input = lambda : sys.stdin.readline().rstrip('\r\n')
		sys.stdout = stream()
		register(lambda : sys.__stdout__.write(sys.stdout.getvalue()))

def main():
	n = int(input())
	a = [int(o) for o in input().split()]
	adj = [[] for i in range(n)]
	vis = [False] * n
	dist = [0] * n
	st = []
	for i in range(n - 1, -1, -1):
		while st and st[-1][0] < a[i]:
			st.pop()
		if st:
			adj[i].append(st[-1][1])
		st.append([a[i], i])
	st = []
	for i in range(n - 1, -1, -1):
		while st and st[-1][0] > a[i]:
			st.pop()
		if st:
			adj[i].append(st[-1][1])
		st.append([a[i], i])
	st = []
	for i in range(n):
		while st and st[-1][0] > a[i]:
			st.pop()
		if st:
			adj[st[-1][1]].append(i)
		st.append([a[i], i])
	st = []
	for i in range(n):
		while st and st[-1][0] < a[i]:
			st.pop()
		if st:
			adj[st[-1][1]].append(i)
		st.append([a[i], i])
	vis[0] = True
	q = deque()
	q.append(0)
	while q:
		so = q.popleft()
		for i in adj[so]:
			if not vis[i]:
				dist[i] = dist[so] + 1
				vis[i] = True
				q.append(i)
	print(dist[n - 1])
sync_with_stdio(False)
main()


def I1():
	n = int(input())
	h = [int(j) for j in input().split()]
	x = [0] * n
	y = [0]
	z = [0]
	for i in range(1, n):
		x[i] = x[i - 1] + 1
		while len(y) and h[i] >= h[y[-1]]:
			a = y[-1]
			y.pop()
			if h[i] > h[a] and len(y):
				x[i] = min(x[i], x[y[-1]] + 1)
		while len(z) and h[i] <= h[z[-1]]:
			a = z[-1]
			z.pop()
			if h[i] < h[a] and len(z):
				x[i] = min(x[i], x[z[-1]] + 1)
		y.append(i)
		z.append(i)
	print(x[-1])
I1()


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import gcd, ceil

def pre(s):
	n = len(s)
	pi = [0] * n
	for i in range(1, n):
		j = pi[i - 1]
		while j and s[i] != s[j]:
			j = pi[j - 1]
		if s[i] == s[j]:
			j += 1
		pi[i] = j
	return pi

def prod(a):
	ans = 1
	for each in a:
		ans = ans * each
	return ans

def lcm(a, b):
	return a * b // gcd(a, b)

def binary(x, length=16):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y
from collections import deque
n = int(input())
a = list(map(int, input().split()))
dp = [10 ** 18] * n
dp[0] = 0
q1 = deque([0])
q2 = deque([0])
for i in range(1, n):
	while q1 and a[i] >= a[q1[-1]]:
		if a[i] > a[q1.pop()] and q1:
			dp[i] = min(dp[i - 1] + 1, dp[q1[-1]] + 1, dp[i])
	q1.append(i)
	while q2 and a[i] <= a[q2[-1]]:
		if a[i] < a[q2.pop()] and q2:
			dp[i] = min(dp[i - 1] + 1, dp[q2[-1]] + 1, dp[i])
	q2.append(i)
	dp[i] = min(dp[i], dp[i - 1] + 1)
print(dp[-1])


n = int(input())
a = list(map(int, input().split()))
dp = [10 ** 9] * n
dp[0] = 0
s1 = [0]
s2 = [0]
for i in range(1, n):
	dp[i] = dp[i - 1] + 1
	(f1, f2) = (True, True)
	while s1 and a[i] >= a[s1[-1]]:
		if a[i] == a[s1[-1]]:
			f1 = False
		dp[i] = min(dp[i], dp[s1[-1]] + 1)
		s1.pop()
	while s2 and a[i] <= a[s2[-1]]:
		if a[i] == a[s2[-1]]:
			f2 = False
		dp[i] = min(dp[i], dp[s2[-1]] + 1)
		s2.pop()
	if s1 and f1:
		dp[i] = min(dp[i], dp[s1[-1]] + 1)
	if s2 and f2:
		dp[i] = min(dp[i], dp[s2[-1]] + 1)
	s1.append(i)
	s2.append(i)
print(dp[n - 1])


class SegmentTree:

	def __init__(self, data, default=0, func=max):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(list(range(_size))):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		start += self._size
		stop += self._size
		res_left = res_right = self._default
		while start < stop:
			if start & 1:
				res_left = self._func(res_left, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res_right = self._func(self.data[stop], res_right)
			start >>= 1
			stop >>= 1
		return self._func(res_left, res_right)

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)
n = int(input())
l = list(map(int, input().split()))
stMax = SegmentTree(l)
stMin = SegmentTree(l, default=10 ** 10, func=min)
nexSmol = [-1] * n
nexTol = [-1] * n
smolS = [n - 1]
tolS = [n - 1]
for i in range(n - 2, -1, -1):
	while smolS and l[smolS[-1]] >= l[i]:
		smolS.pop()
	if smolS:
		nexSmol[i] = smolS[-1]
	smolS.append(i)
	while tolS and l[tolS[-1]] <= l[i]:
		tolS.pop()
	if tolS:
		nexTol[i] = tolS[-1]
	tolS.append(i)
best = [n] * n
best[0] = 0
for i in range(n - 1):
	curr = best[i]
	if l[i + 1] > l[i]:
		reach = i + 1
		best[i + 1] = min(curr + 1, best[i + 1])
		while nexSmol[reach] != -1:
			reach = nexSmol[reach]
			if stMin.query(i + 1, reach) < l[i]:
				break
			best[reach] = min(curr + 1, best[reach])
	elif l[i + 1] < l[i]:
		reach = i + 1
		best[i + 1] = min(curr + 1, best[i + 1])
		while nexTol[reach] != -1:
			reach = nexTol[reach]
			if stMax.query(i + 1, reach) > l[i]:
				break
			best[reach] = min(curr + 1, best[reach])
	else:
		best[i + 1] = min(curr + 1, best[i + 1])
print(best[-1])


n = int(input())
inp = input().split(' ')
h = []
for i in inp:
	h.append(int(i))
arr = []
for i in range(n):
	arr.append(i)
arr[0] = 0
high = []
low = []
for i in range(n):
	flag = True
	while high and h[high[-1]] >= h[i]:
		val = high.pop()
		arr[i] = min(arr[i], arr[val] + 1)
		if h[i] == h[val]:
			flag = False
		else:
			flag = True
	if high and flag:
		arr[i] = min(arr[high[-1]] + 1, arr[i])
	while low and h[low[-1]] <= h[i]:
		val = low.pop()
		arr[i] = min(arr[i], arr[val] + 1)
		if h[i] == h[val]:
			flag = False
		else:
			flag = True
	if low and flag:
		arr[i] = min(arr[low[-1]] + 1, arr[i])
	high.append(i)
	low.append(i)
print(arr[-1])


import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
inf = N + 1
dp = [inf] * N
dp[0] = 0
ups = []
dws = []
for i in range(N):
	x = a[i]
	f = 1
	while len(ups) > 0 and a[ups[-1]] >= x:
		j = ups.pop()
		dp[i] = min(dp[i], dp[j] + 1)
		f = a[j] != x
	if f and len(ups) > 0:
		dp[i] = min(dp[i], dp[ups[-1]] + 1)
	f = 1
	while len(dws) > 0 and a[dws[-1]] <= x:
		j = dws.pop()
		dp[i] = min(dp[i], dp[j] + 1)
		f = a[j] != x
	if f and len(dws) > 0:
		dp[i] = min(dp[i], dp[dws[-1]] + 1)
	ups.append(i)
	dws.append(i)
print(dp[-1])


import sys
input = sys.stdin.readline
import sys
import heapq
import copy
import math
import decimal

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def insr2():
	s = input()
	return s[:len(s) - 1]

def invr():
	return map(int, input().split())
ans = 0

def pr_list(a):
	print(*a, sep=' ')

def swap(a, b):
	temp = a
	a = b
	b = temp
	return [a, b]

def pri(a, b):
	s = '? ' + str(a) + ' ' + str(b)
	print(s)
	sys.stdout.flush()

def main():
	tests = 1
	mod = 1000000007
	limit = 10 ** 18
	ans = 0
	stack = []
	hashm = {}
	arr = []
	heapq.heapify(arr)
	for test in range(tests):
		n = inp()
		h = inlt()
		edges = [{} for i in range(n)]
		stack = []
		i = 0
		while i < n:
			if stack == []:
				stack.append(i)
				i = i + 1
				continue
			while stack != [] and h[stack[-1]] > h[i]:
				dum = stack.pop()
			if stack != []:
				edges[stack[-1]][i] = 1
			stack.append(i)
			i = i + 1
		stack = []
		i = 0
		while i < n:
			if stack == []:
				stack.append(i)
				i = i + 1
				continue
			while stack != [] and h[stack[-1]] < h[i]:
				dum = stack.pop()
			if stack != []:
				edges[stack[-1]][i] = 1
			stack.append(i)
			i = i + 1
		stack = []
		i = n - 1
		while i >= 0:
			if stack == []:
				stack.append(i)
				i = i - 1
				continue
			while stack != [] and h[stack[-1]] > h[i]:
				dum = stack.pop()
			if stack != []:
				edges[i][stack[-1]] = 1
			stack.append(i)
			i = i - 1
		stack = []
		i = n - 1
		while i >= 0:
			if stack == []:
				stack.append(i)
				i = i - 1
				continue
			while stack != [] and h[stack[-1]] < h[i]:
				dum = stack.pop()
			if stack != []:
				edges[i][stack[-1]] = 1
			stack.append(i)
			i = i - 1
		dp = [sys.maxsize for i in range(n)]
		dp[0] = 0
		for i in range(n - 1):
			dp[i + 1] = min(dp[i + 1], dp[i] + 1)
			for j in edges[i]:
				dp[j] = min(dp[j], dp[i] + 1)
		print(dp[n - 1])
main()


from collections import deque
import sys
input = sys.stdin.readline
n = int(input())
a = [int(i) for i in input().split() if i != '\n']
d = [set() for i in range(n)]
stack = []
for i in range(n):
	while stack and stack[-1][0] > a[i]:
		stack.pop()
	if stack:
		d[stack[-1][1]].add(i)
	stack.append((a[i], i))
stack = []
for i in range(n):
	while stack and stack[-1][0] < a[i]:
		stack.pop()
	if stack:
		d[stack[-1][1]].add(i)
	stack.append((a[i], i))
stack = []
for i in range(n - 1, -1, -1):
	while stack and stack[-1][0] > a[i]:
		stack.pop()
	if stack:
		d[i].add(stack[-1][1])
	stack.append((a[i], i))
stack = []
for i in range(n - 1, -1, -1):
	while stack and stack[-1][0] < a[i]:
		stack.pop()
	if stack:
		d[i].add(stack[-1][1])
	stack.append((a[i], i))
queue = deque([0])
dist = [0] * n
visited = set()
while queue:
	vertex = queue.popleft()
	for child in d[vertex]:
		if child in visited:
			continue
		else:
			dist[child] = dist[vertex] + 1
			queue.append(child)
			visited.add(child)
print(dist[-1])


def rainy(L, N):
	jumps = [0] * N
	jI = [0]
	jJ = [0]
	for i in range(1, N):
		jumps[i] = jumps[i - 1] + 1
		while len(jI) > 0 and L[i] >= L[jI[-1]]:
			temp = jI[-1]
			jI.pop()
			if L[i] > L[temp] and len(jI) > 0:
				jumps[i] = min(jumps[i], jumps[jI[-1]] + 1)
		while len(jJ) > 0 and L[i] <= L[jJ[-1]]:
			temp = jJ[-1]
			jJ.pop()
			if L[i] < L[temp] and len(jJ) > 0:
				jumps[i] = min(jumps[i], jumps[jJ[-1]] + 1)
		jI.append(i)
		jJ.append(i)
	return jumps[-1]
SIZE = int(input())
L = list(map(int, input().split()))
print(rainy(L, SIZE))


import os, sys
from io import BytesIO, IOBase

def main():
	n = int(input())
	h = list(map(int, input().split()))
	max_st = [-1] * n
	min_st = [-1] * n
	for i in range(n - 2, -1, -1):
		if h[i] >= h[i + 1]:
			min_st[i] = i + 1
		else:
			x = min_st[i + 1]
			while x != -1 and h[i] < h[x]:
				x = min_st[x]
			min_st[i] = x
		if h[i] <= h[i + 1]:
			max_st[i] = i + 1
		else:
			x = max_st[i + 1]
			while x != -1 and h[i] > h[x]:
				x = max_st[x]
			max_st[i] = x
	max_st1 = [-1] * n
	min_st1 = [-1] * n
	for i in range(1, n):
		if h[i] >= h[i - 1]:
			min_st1[i] = i - 1
		else:
			x = min_st1[i - 1]
			while x != -1 and h[i] < h[x]:
				x = min_st1[x]
			min_st1[i] = x
		if h[i] <= h[i - 1]:
			max_st1[i] = i - 1
		else:
			x = max_st1[i - 1]
			while x != -1 and h[i] > h[x]:
				x = max_st1[x]
			max_st1[i] = x
	rishta = [[] for _ in range(n)]
	for (i, val) in enumerate(min_st):
		if val != -1:
			rishta[i].append(val)
			rishta[val].append(i)
	for (i, val) in enumerate(min_st1):
		if val != -1:
			rishta[i].append(val)
			rishta[val].append(i)
	for (i, val) in enumerate(max_st):
		if val != -1:
			rishta[i].append(val)
			rishta[val].append(i)
	for (i, val) in enumerate(max_st1):
		if val != -1:
			rishta[i].append(val)
			rishta[val].append(i)
	lst = [10 ** 10] * n
	lst[0] = 0
	for i in range(n - 1):
		lst[i + 1] = min(lst[i + 1], lst[i] + 1)
		for x in rishta[i]:
			if x > i:
				lst[x] = min(lst[x], lst[i] + 1)
	print(lst[-1])
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


ans = []
n = int(input())
h = [int(x) for x in input().split(' ')]
jumps = [0] * n
build_ctr_short = [0]
build_ctr_tall = [0]
for i in range(1, n):
	jumps[i] = jumps[i - 1] + 1
	while len(build_ctr_short) and h[i] >= h[build_ctr_short[-1]]:
		build_num = build_ctr_short[-1]
		build_ctr_short.pop()
		if h[i] > h[build_num] and len(build_ctr_short):
			jumps[i] = min(jumps[i], jumps[build_ctr_short[-1]] + 1)
	while len(build_ctr_tall) and h[i] <= h[build_ctr_tall[-1]]:
		build_num = build_ctr_tall[-1]
		build_ctr_tall.pop()
		if h[i] < h[build_num] and len(build_ctr_tall):
			jumps[i] = min(jumps[i], jumps[build_ctr_tall[-1]] + 1)
	build_ctr_short.append(i)
	build_ctr_tall.append(i)
ans.append(jumps[-1])
for i in ans:
	print(i)


import collections
N = int(input())
A = list(map(int, input().split()))
G = [set() for i in range(N)]
for i in range(N - 1):
	G[i].add(i + 1)
stack = collections.deque()
for (i, a) in enumerate(A):
	while stack and stack[-1][0] < a:
		stack.pop()
	if stack:
		G[stack[-1][1]].add(i)
	stack.append((a, i))
stack.clear()
for (i, a) in enumerate(A):
	while stack and stack[-1][0] > a:
		stack.pop()
	if stack:
		G[stack[-1][1]].add(i)
	stack.append((a, i))
stack.clear()
for i in range(N - 1, -1, -1):
	while stack and stack[-1][0] < A[i]:
		stack.pop()
	if stack:
		G[i].add(stack[-1][1])
	stack.append((A[i], i))
stack.clear()
for i in range(N - 1, -1, -1):
	while stack and stack[-1][0] > A[i]:
		stack.pop()
	if stack:
		G[i].add(stack[-1][1])
	stack.append((A[i], i))
queue = collections.deque()
visited = [False for _ in G]
queue.append((0, 0))
visited[0] = True
while queue:
	(item, step) = queue.popleft()
	for c in G[item]:
		if not visited[c]:
			visited[c] = True
			queue.append((c, step + 1))
			if c == N - 1:
				print(step + 1)
				exit()


import sys, heapq
input = sys.stdin.buffer.readline
n = int(input())
ls = list(map(int, input().split()))
dp = [n] * n
dp[n - 1] = 0
(up, dn) = ([n - 1], [n - 1])
for p in range(n - 2, -1, -1):
	u = ls[p]
	while up and ls[up[-1]] > u:
		dp[p] = min(dp[p], dp[up[-1]] + 1)
		up.pop()
	if up:
		dp[p] = min(dp[p], dp[up[-1]] + 1)
	while dn and ls[dn[-1]] < u:
		dp[p] = min(dp[p], dp[dn[-1]] + 1)
		dn.pop()
	if dn:
		dp[p] = min(dp[p], dp[dn[-1]] + 1)
	up.append(p)
	if len(up) > 1 and ls[up[-1]] == ls[up[-2]]:
		up.pop()
		up[-1] = p
	dn.append(p)
	if len(dn) > 1 and ls[dn[-1]] == ls[dn[-2]]:
		dn.pop()
		dn[-1] = p
print(dp[0])


import operator as ops
from collections import deque
from itertools import chain

def construct_links(h_and_idx):
	lt_stack = []
	gt_stack = []
	g = [[] for _ in h_and_idx]
	for (h, idx) in reversed(h_and_idx):
		for (stack, cmp_op) in [(lt_stack, ops.le), (gt_stack, ops.ge)]:
			prev_h = None
			while stack and cmp_op(h, stack[-1][0]):
				(prev_h, prev_idx) = stack.pop()
				g[idx].append(prev_idx)
			if stack and prev_h != h:
				g[idx].append(stack[-1][1])
			stack.append((h, idx))
	return g

def main():
	n = int(input())
	h_and_idx = tuple(((h, i) for (i, h) in enumerate(map(int, input().split()))))
	g = construct_links(h_and_idx)
	dist = [0] + [-1] * (n - 1)
	q = deque([0], n)
	while q:
		v = q.popleft()
		for x in g[v]:
			if dist[x] == -1:
				dist[x] = dist[v] + 1
				q.append(x)
	print(dist[-1])
main()


def answer(n, A):
	l = [0]
	g = [0]
	dp = [float('inf')] * n
	dp[0] = 0
	for i in range(1, n):
		flag = 1
		while g and A[g[-1]] >= A[i]:
			index = g.pop()
			dp[i] = min(dp[i], dp[index] + 1)
			if A[i] == A[index]:
				flag = 0
			else:
				flag = 1
		if g and flag:
			dp[i] = min(dp[i], dp[g[-1]] + 1)
		flag = 1
		while l and A[l[-1]] <= A[i]:
			index = l.pop()
			dp[i] = min(dp[i], dp[index] + 1)
			if A[i] == A[index]:
				flag = 0
			else:
				flag = 1
		if l and flag:
			dp[i] = min(dp[i], dp[l[-1]] + 1)
		l.append(i)
		g.append(i)
	return dp[n - 1]
n = int(input())
arr = list(map(int, input().split()))
print(answer(n, arr))


n = int(input())
h = list(map(int, input().split()))
incrStack = [0]
decrStack = [0]
dp = [-1] * n
dp[0] = 0
for i in range(1, n):
	dp[i] = dp[i - 1]
	equalFound = False
	while incrStack and h[i] <= h[incrStack[-1]]:
		curElem = incrStack.pop()
		if not equalFound and h[i] < h[i - 1]:
			dp[i] = min(dp[i], dp[curElem])
		if h[curElem] == h[i]:
			equalFound = True
	if not equalFound and incrStack and (h[i] < h[i - 1]):
		dp[i] = min(dp[i], dp[incrStack[-1]])
	incrStack.append(i)
	equalFound = False
	while decrStack and h[i] >= h[decrStack[-1]]:
		curElem = decrStack.pop()
		if not equalFound and h[i] > h[i - 1]:
			dp[i] = min(dp[i], dp[curElem])
		if h[curElem] == h[i]:
			equalFound = True
	if not equalFound and decrStack and (h[i] > h[i - 1]):
		dp[i] = min(dp[i], dp[decrStack[-1]])
	decrStack.append(i)
	dp[i] += 1
print(dp[-1])


def empty(l):
	if len(l) == 0:
		return True
	return False
n = int(input())
h = list(map(int, input().split(' ')))
(inc, dec) = ([0], [0])
dp = [0] * n
for i in range(1, n):
	(f1, f2) = (0, 0)
	dp[i] = dp[i - 1] + 1
	while not empty(inc) and h[i] >= h[inc[-1]]:
		x = h[inc[-1]]
		inc.pop()
		if h[i] > x and (not empty(inc)):
			dp[i] = min(dp[i], dp[inc[-1]] + 1)
	while not empty(dec) and h[i] <= h[dec[-1]]:
		x = h[dec[-1]]
		dec.pop()
		if h[i] < x and (not empty(dec)):
			dp[i] = min(dp[i], dp[dec[-1]] + 1)
	inc.append(i)
	dec.append(i)
print(dp[-1])


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

def RLL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def N():
	return int(input())

def print_list(l):
	print(' '.join(map(str, l)))
n = int(input())
a = RLL()
dp = [0] * n
high = [n - 1]
low = [n - 1]
for i in range(n - 2, -1, -1):
	dp[i] = dp[i + 1] + 1
	if a[i] > a[i + 1]:
		high.pop()
		while high and a[high[-1]] < a[i]:
			dp[i] = min(dp[i], dp[high[-1]] + 1)
			high.pop()
		if high:
			dp[i] = min(dp[i], dp[high[-1]] + 1)
			if a[high[-1]] == a[i]:
				high.pop()
	elif a[i] < a[i + 1]:
		low.pop()
		while low and a[low[-1]] > a[i]:
			dp[i] = min(dp[i], dp[low[-1]] + 1)
			low.pop()
		if low:
			dp[i] = min(dp[i], dp[low[-1]] + 1)
			if a[low[-1]] == a[i]:
				low.pop()
	else:
		dp[i] = dp[i + 1] + 1
		high.pop()
		low.pop()
	high.append(i)
	low.append(i)
print(dp[0])


try:
	n = int(input())
	a = [int(i) for i in input().split(' ')]
	dp = [n] * n
	dp[0] = 0
	(s1, s2) = ([], [])
	s1.append(0)
	s2.append(0)
	i = 1
	while i < n:
		dp[i] = dp[i - 1] + 1
		while s1 and a[i] <= a[s1[len(s1) - 1]]:
			item = a[s1[len(s1) - 1]]
			s1.pop()
			if a[i] < item and s1:
				dp[i] = min(dp[i], dp[s1[len(s1) - 1]] + 1)
		while s2 and a[i] >= a[s2[len(s2) - 1]]:
			item = a[s2[len(s2) - 1]]
			s2.pop()
			if a[i] > item and s2:
				dp[i] = min(dp[i], dp[s2[len(s2) - 1]] + 1)
		s1.append(i)
		s2.append(i)
		i += 1
	print(dp[n - 1])
except:
	pass


import collections
l = int(input())
s = list(map(int, input().split()))
dp = [float('inf') for i in range(l + 1)]
dp = [float('inf') for i in range(l + 1)]
dp[1] = 0
st1 = collections.deque()
st2 = collections.deque()
for (i, n) in enumerate(s):
	if len(st1) == 1 or (len(st1) > 0 and s[st1[1]] < n):
		dp[i + 1] = min(dp[st1[0] + 1] + 1, dp[i + 1])
	c = 1
	while st1 and s[st1[-1]] <= n:
		if s[st1[-1]] == n:
			c = 0
		dp[i + 1] = min(dp[i + 1], dp[st1.pop() + 1] + 1)
	if st1 and c:
		dp[i + 1] = min(dp[i + 1], dp[st1[-1] + 1] + 1)
	st1.append(i)
	if len(st2) == 1 or (len(st2) > 0 and s[st2[1]] > n):
		dp[i + 1] = min(dp[st2[0] + 1] + 1, dp[i + 1])
	c = 1
	while st2 and s[st2[-1]] >= n:
		if s[st2[-1]] == n:
			c = 0
		dp[i + 1] = min(dp[i + 1], dp[st2.pop() + 1] + 1)
	if st2 and c == 1:
		dp[i + 1] = min(dp[i + 1], dp[st2[-1] + 1] + 1)
	st2.append(i)
print(dp[-1])


class SegmentTree:

	def __init__(self, init_val, segfunc, ide_ele):
		n = len(init_val)
		self.segfunc = segfunc
		self.ide_ele = ide_ele
		self.num = 1 << (n - 1).bit_length()
		self.tree = [ide_ele] * 2 * self.num
		self.range = [(-1, n)] * 2 * self.num
		for i in range(n):
			self.tree[self.num + i] = init_val[i]
			self.range[self.num + i] = (i, i)
		for i in range(self.num - 1, 0, -1):
			self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])
			self.range[i] = (self.range[2 * i][0], self.range[2 * i + 1][1])

	def update(self, k, x):
		k += self.num
		self.tree[k] = x
		while k > 1:
			self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
			k >>= 1

	def query(self, l, r):
		res = self.ide_ele
		l += self.num
		r += self.num
		while l < r:
			if l & 1:
				res = self.segfunc(res, self.tree[l])
				l += 1
			if r & 1:
				res = self.segfunc(res, self.tree[r - 1])
			l >>= 1
			r >>= 1
		return res
import sys
input = sys.stdin.buffer.readline
n = int(input())
N = n
h = list(map(int, input().split()))
left_high = [i for i in range(n)]
stack = [n - 1]
for i in range(n - 2, -1, -1):
	while stack and h[stack[-1]] >= h[i]:
		left_high[stack[-1]] = i + 1
		stack.pop()
	stack.append(i)
while stack:
	left_high[stack[-1]] = 0
	stack.pop()
left_low = [i for i in range(n)]
stack = [n - 1]
for i in range(n - 2, -1, -1):
	while stack and h[stack[-1]] <= h[i]:
		left_low[stack[-1]] = i + 1
		stack.pop()
	stack.append(i)
while stack:
	left_low[stack[-1]] = 0
	stack.pop()
right_high = [i for i in range(n)]
stack = [0]
for i in range(1, n):
	while stack and h[stack[-1]] >= h[i]:
		right_high[stack[-1]] = i
		stack.pop()
	stack.append(i)
while stack:
	right_high[stack[-1]] = N - 1
	stack.pop()
right_low = [i for i in range(n)]
stack = [0]
for i in range(1, n):
	while stack and h[stack[-1]] <= h[i]:
		right_low[stack[-1]] = i
		stack.pop()
	stack.append(i)
while stack:
	right_low[stack[-1]] = N - 1
	stack.pop()
dp = [10 ** 9 for i in range(n)]
dp_high_seg = SegmentTree(dp, min, 10 ** 9)
dp_low_seg = SegmentTree(dp, min, 10 ** 9)
dp[-1] = 0
high_query = [(i, i) for i in range(n)]
for i in range(n):
	high_query.append((left_high[i] - 1, -i))
high_query.sort()
low_query = [(i, i) for i in range(n)]
for i in range(n):
	low_query.append((left_low[i] - 1, -i))
low_query.sort()
for i in range(n - 2, -1, -1):
	while high_query and high_query[-1][0] > i:
		(t, idx) = high_query.pop()
		if idx > 0:
			dp_high_seg.update(idx, dp[idx])
		else:
			dp_high_seg.update(-idx, 10 ** 9)
	while low_query and low_query[-1][0] > i:
		(t, idx) = low_query.pop()
		if idx > 0:
			dp_low_seg.update(idx, dp[idx])
		else:
			dp_low_seg.update(-idx, 10 ** 9)
	if h[i] < h[i + 1]:
		R = right_high[i]
		dp[i] = min(dp[i + 1], dp_high_seg.query(i + 1, R + 1)) + 1
	elif h[i] == h[i + 1]:
		dp[i] = dp[i + 1] + 1
	else:
		R = right_low[i]
		dp[i] = min(dp[i + 1], dp_low_seg.query(i + 1, R + 1)) + 1
print(dp[0])


from bisect import *
from collections import *
from math import gcd, ceil, sqrt, floor, inf
from heapq import *
from itertools import *
from operator import add, mul, sub, xor, truediv, floordiv
from functools import *
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

def RLL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def N():
	return int(input())
from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc
farr = [1]
ifa = []

def fact(x, mod=0):
	if mod:
		while x >= len(farr):
			farr.append(farr[-1] * len(farr) % mod)
	else:
		while x >= len(farr):
			farr.append(farr[-1] * len(farr))
	return farr[x]

def ifact(x, mod):
	global ifa
	ifa.append(pow(farr[-1], mod - 2, mod))
	for i in range(x, 0, -1):
		ifa.append(ifa[-1] * i % mod)
	ifa = ifa[::-1]

def per(i, j, mod=0):
	if i < j:
		return 0
	if not mod:
		return fact(i) // fact(i - j)
	return farr[i] * ifa[i - j] % mod

def com(i, j, mod=0):
	if i < j:
		return 0
	if not mod:
		return per(i, j) // fact(j)
	return per(i, j, mod) * ifa[j] % mod

def catalan(n):
	return com(2 * n, n) // (n + 1)

def linc(f, t, l, r):
	while l < r:
		mid = (l + r) // 2
		if t > f(mid):
			l = mid + 1
		else:
			r = mid
	return l

def rinc(f, t, l, r):
	while l < r:
		mid = (l + r + 1) // 2
		if t < f(mid):
			r = mid - 1
		else:
			l = mid
	return l

def ldec(f, t, l, r):
	while l < r:
		mid = (l + r) // 2
		if t < f(mid):
			l = mid + 1
		else:
			r = mid
	return l

def rdec(f, t, l, r):
	while l < r:
		mid = (l + r + 1) // 2
		if t > f(mid):
			r = mid - 1
		else:
			l = mid
	return l

def isprime(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return True

def binfun(x):
	c = 0
	for w in arr:
		c += ceil(w / x)
	return c

def lowbit(n):
	return n & -n

def inverse(a, m):
	a %= m
	if a <= 1:
		return a
	return (1 - inverse(m, a) * m) // a % m

class BIT:

	def __init__(self, arr):
		self.arr = arr
		self.n = len(arr) - 1

	def update(self, x, v):
		while x <= self.n:
			self.arr[x] += v
			x += x & -x

	def query(self, x):
		ans = 0
		while x:
			ans += self.arr[x]
			x &= x - 1
		return ans

class smt:

	def __init__(self, l, r, arr):
		self.l = l
		self.r = r
		self.value = (1 << 31) - 1 if l < r else arr[l]
		mid = (l + r) // 2
		if l < r:
			self.left = smt(l, mid, arr)
			self.right = smt(mid + 1, r, arr)
			self.value &= self.left.value & self.right.value

	def setvalue(self, x, val):
		if self.l == self.r:
			self.value = val
			return
		mid = (self.l + self.r) // 2
		if x <= mid:
			self.left.setvalue(x, val)
		else:
			self.right.setvalue(x, val)
		self.value = self.left.value & self.right.value

	def ask(self, l, r):
		if l <= self.l and r >= self.r:
			return self.value
		val = (1 << 31) - 1
		mid = (self.l + self.r) // 2
		if l <= mid:
			val &= self.left.ask(l, r)
		if r > mid:
			val &= self.right.ask(l, r)
		return val

class DSU:

	def __init__(self, n):
		self.c = [-1] * n

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def find(self, x):
		if self.c[x] < 0:
			return x
		self.c[x] = self.find(self.c[x])
		return self.c[x]

	def union(self, u, v):
		(u, v) = (self.find(u), self.find(v))
		if u == v:
			return False
		if self.c[u] < self.c[v]:
			(u, v) = (v, u)
		self.c[u] += self.c[v]
		self.c[v] = u
		return True

	def size(self, x):
		return -self.c[self.find(x)]

class UFS:

	def __init__(self, n):
		self.parent = [i for i in range(n)]
		self.ranks = [0] * n

	def find(self, x):
		if x != self.parent[x]:
			self.parent[x] = self.find(self.parent[x])
		return self.parent[x]

	def union(self, u, v):
		(pu, pv) = (self.find(u), self.find(v))
		if pu == pv:
			return False
		if self.ranks[pu] >= self.ranks[pv]:
			self.parent[pv] = pu
			if self.ranks[pv] == self.ranks[pu]:
				self.ranks[pu] += 1
		else:
			self.parent[pu] = pv

def Prime(n):
	c = 0
	prime = []
	flag = [0] * (n + 1)
	for i in range(2, n + 1):
		if not flag[i]:
			prime.append(i)
			c += 1
		for j in range(c):
			if i * prime[j] > n:
				break
			flag[i * prime[j]] = prime[j]
			if i % prime[j] == 0:
				break
	return prime

def dij(s, graph):
	d = {}
	d[s] = 0
	heap = [(0, s)]
	seen = set()
	while heap:
		(dis, u) = heappop(heap)
		if u in seen:
			continue
		for v in graph[u]:
			if v not in d or d[v] > d[u] + graph[u][v]:
				d[v] = d[u] + graph[u][v]
				heappush(heap, (d[v], v))
	return d

def GP(it):
	return [(ch, len(list(g))) for (ch, g) in groupby(it)]

class DLN:

	def __init__(self, val):
		self.val = val
		self.pre = None
		self.next = None

def query(x, y):
	print('?', x, y)
	sys.stdout.flush()
	return N()
t = 1
for i in range(t):
	n = N()
	h = RLL()
	res = [[] for i in range(n)]
	stack = []
	for i in range(n):
		flag = True
		while stack and h[stack[-1]] <= h[i]:
			cur = stack.pop()
			res[i].append(cur)
			if h[cur] == h[i]:
				flag = False
		if flag and stack:
			res[i].append(stack[-1])
		stack.append(i)
	stack = []
	for i in range(n):
		flag = True
		while stack and h[stack[-1]] >= h[i]:
			cur = stack.pop()
			res[i].append(cur)
			if h[cur] == h[i]:
				flag = False
		if flag and stack:
			res[i].append(stack[-1])
		stack.append(i)
	dp = [inf] * n
	dp[0] = 0
	for i in range(1, n):
		for j in res[i]:
			dp[i] = min(dp[i], dp[j] + 1)
	ans = dp[-1]
	print(ans)


import sys, math
import io, os
from bisect import bisect_left as bl, bisect_right as br, insort
from heapq import heapify, heappush, heappop
from collections import defaultdict as dd, deque, Counter

def data():
	return sys.stdin.readline().strip()

def mdata():
	return list(map(int, data().split()))

def outl(var):
	sys.stdout.write(' '.join(map(str, var)) + '\n')

def out(var):
	sys.stdout.write(str(var) + '\n')
INF = float('inf')
mod = 10 ** 9 + 7
n = int(data())
h = mdata()
stack1 = [h[0]]
stack2 = [h[0]]
d = dd(int)
for i in range(1, n):
	k = INF
	while stack1 and stack1[-1] > h[i]:
		if stack1[-1] < h[i - 1]:
			k = min(k, d[stack1[-1]])
		stack1.pop()
	while stack2 and stack2[-1] < h[i]:
		if stack2[-1] > h[i - 1]:
			k = min(k, d[stack2[-1]])
		stack2.pop()
	if stack1:
		k = min(k, d[stack1[-1]])
	if stack2:
		k = min(k, d[stack2[-1]])
	d[h[i]] = k + 1
	stack1.append(h[i])
	stack2.append(h[i])
out(d[h[-1]])


import sys
input = sys.stdin.readline
n = int(input())
h = list(map(int, input().split()))
prev_small = [-1] * n
stack = []
for i in range(n):
	while stack and stack[-1][0] > h[i]:
		stack.pop()
	if stack:
		prev_small[i] = stack[-1][1]
	stack.append([h[i], i])
prev_large = [-1] * n
stack = []
for i in range(n):
	while stack and stack[-1][0] < h[i]:
		stack.pop()
	if stack:
		prev_large[i] = stack[-1][1]
	stack.append([h[i], i])
next_small = [-1] * n
stack = []
for i in range(n)[::-1]:
	while stack and stack[-1][0] > h[i]:
		stack.pop()
	if stack:
		next_small[i] = stack[-1][1]
	stack.append([h[i], i])
next_large = [-1] * n
stack = []
for i in range(n)[::-1]:
	while stack and stack[-1][0] < h[i]:
		stack.pop()
	if stack:
		next_large[i] = stack[-1][1]
	stack.append([h[i], i])
can = [[] for i in range(n)]
for i in range(n):
	if prev_small[i] >= 0:
		can[prev_small[i]].append(i)
	if prev_large[i] >= 0:
		can[prev_large[i]].append(i)
	if next_small[i] >= 0:
		can[i].append(next_small[i])
	if next_large[i] >= 0:
		can[i].append(next_large[i])
dp = [10 ** 9] * n
dp[0] = 0
for i in range(n):
	for j in can[i]:
		dp[j] = min(dp[j], dp[i] + 1)
print(dp[n - 1])


mod = 1000000007
eps = 10 ** (-9)
inf = 10 ** 9

def main():
	import sys
	input = sys.stdin.readline

	class Bit:

		def __init__(self, n):
			self.size = n
			self.tree = [0] * (n + 1)

		def sum(self, i):
			s = 0
			while i > 0:
				s += self.tree[i]
				i -= i & -i
			return s

		def add(self, i, x):
			while i <= self.size:
				self.tree[i] += x
				i += i & -i

		def lower_bound(self, w):
			if w <= 0:
				return 0
			x = 0
			k = 1 << self.size.bit_length() - 1
			while k:
				if x + k <= self.size and self.tree[x + k] < w:
					w -= self.tree[x + k]
					x += k
				k >>= 1
			return x + 1
	N = int(input())
	A = list(map(int, input().split()))
	adj = [[] for _ in range(N + 1)]
	AA = sorted(list(set(A)))
	a2i = {a: i for (i, a) in enumerate(AA)}
	AI = [[] for _ in range(len(AA))]
	for (i, a) in enumerate(A):
		ii = a2i[a]
		AI[ii].append(i + 1)
	bit_high = Bit(N)
	for i_list in AI:
		for i in i_list:
			bit_high.add(i, 1)
		for i in i_list:
			val = bit_high.sum(i)
			il = bit_high.lower_bound(val - 1)
			ir = bit_high.lower_bound(val + 1)
			if il > 0:
				adj[il].append(i)
			if ir <= N:
				adj[i].append(ir)
	bit_low = Bit(N)
	AI.reverse()
	for i_list in AI:
		for i in i_list:
			bit_low.add(i, 1)
		for i in i_list:
			val = bit_low.sum(i)
			il = bit_low.lower_bound(val - 1)
			ir = bit_low.lower_bound(val + 1)
			if il > 0:
				adj[il].append(i)
			if ir <= N:
				adj[i].append(ir)
	dp = [inf] * (N + 1)
	dp[1] = 0
	for i in range(1, N + 1):
		for j in adj[i]:
			dp[j] = min(dp[j], dp[i] + 1)
	print(dp[N])

def __starting_point():
	main()
__starting_point()


import io
import os
import sys
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def printd(*args, **kwargs):
	pass

def get_str():
	return input().decode().strip()

def rint():
	return map(int, input().split())

def oint():
	return int(input())

def solve():
	n = oint()
	h = list(rint())
	pair = [{i + 1} for i in range(n)]
	pair[n - 1] = set()
	st = [[h[0], 0]]
	for i in range(1, n):
		while st and st[-1][0] <= h[i]:
			pair[st[-1][1]].add(i)
			st.pop()
		st.append([h[i], i])
	st = [[h[-1], n - 1]]
	for i in range(n - 2, -1, -1):
		while st and st[-1][0] <= h[i]:
			pair[i].add(st[-1][1])
			st.pop()
		st.append([h[i], i])
	st = [[h[-1], n - 1]]
	for i in range(n - 2, -1, -1):
		while st and st[-1][0] >= h[i]:
			pair[i].add(st[-1][1])
			st.pop()
		st.append([h[i], i])
	st = [[h[0], 0]]
	for i in range(1, n):
		while st and st[-1][0] >= h[i]:
			pair[st[-1][1]].add(i)
			st.pop()
		st.append([h[i], i])
	dp = [float('inf')] * n
	dp[0] = 0
	for (i, js) in enumerate(pair):
		for j in js:
			dp[j] = min(dp[j], dp[i] + 1)
	printd(h)
	printd(pair)
	printd(dp)
	print(dp[-1])
solve()


from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase
from itertools import *
import bisect
from heapq import *
from math import *
from copy import *
from collections import deque
from collections import Counter as counter
from itertools import combinations as comb
from itertools import permutations as permutate
from bisect import bisect_left as bl
from bisect import bisect_right as br
from bisect import bisect
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
from types import GeneratorType

def iterative(f, stack=[]):

	def wrapped_func(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		to = f(*args, **kwargs)
		while True:
			if type(to) is GeneratorType:
				stack.append(to)
				to = next(to)
				continue
			stack.pop()
			if not stack:
				break
			to = stack[-1].send(to)
		return to
	return wrapped_func
mod = 1000000007

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def zerolist(n):
	return [0] * n

def nextline():
	out('\n')

def testcase(t):
	for pp in range(t):
		solve(pp)

def printlist(a):
	for p in range(0, len(a)):
		out(str(a[p]) + ' ')

def google(p):
	print('Case #' + str(p) + ': ', end='')

def lcm(a, b):
	return a * b // gcd(a, b)

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def ncr(n, r):
	return factorial(n) // (factorial(r) * factorial(max(n - r, 1)))

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True

def bfs(g, st):
	visited = [-1] * len(g)
	visited[st] = 0
	queue = deque([])
	queue.append(st)
	new = []
	while len(queue) != 0:
		s = queue.popleft()
		new.append(s)
		for i in g[s]:
			if visited[i] == -1:
				visited[i] = visited[s] + 1
				queue.append(i)
	return visited[-1]

def solve(case):
	n = int(inp())
	h = lis()
	new = []
	for i in range(n):
		new.append([h[i], i])
	g = [[] for i in range(n)]
	stack = deque([])
	for i in range(n):
		while len(stack) != 0 and new[stack[-1]][0] < new[i][0]:
			g[stack[-1]].append(i)
			stack.pop()
		if len(stack) != 0:
			g[stack[-1]].append(i)
		if len(stack) != 0 and new[stack[-1]][0] == new[i][0]:
			stack.pop()
		stack.append(i)
	for i in range(n):
		new[i][0] = new[i][0] * -1
	stack = deque([])
	for i in range(n):
		while len(stack) != 0 and new[stack[-1]][0] < new[i][0]:
			g[stack[-1]].append(i)
			stack.pop()
		if len(stack) != 0:
			g[stack[-1]].append(i)
		if len(stack) != 0 and new[stack[-1]][0] == new[i][0]:
			stack.pop()
		stack.append(i)
	print(bfs(g, 0))
testcase(1)


import io
import os
from collections import Counter, defaultdict, deque
NONE = -1

def buildFirstBiggerOrEqualLeft(arr):
	ret = [NONE] * len(arr)
	window = []
	for (i, x) in enumerate(arr):
		while window and arr[window[-1]] < x:
			window.pop()
		if window:
			assert arr[window[-1]] >= x
			ret[i] = window[-1]
		window.append(i)
	return ret

def buildFirstSmallerOrEqualLeft(arr):
	return buildFirstBiggerOrEqualLeft([-x for x in arr])

def buildFirstBiggerOrEqualRight(arr):
	N = len(arr)
	return [N - 1 - i if i != NONE else NONE for i in buildFirstBiggerOrEqualLeft(arr[::-1])[::-1]]

def buildFirstSmallerOrEqualRight(arr):
	N = len(arr)
	return [N - 1 - i if i != NONE else NONE for i in buildFirstSmallerOrEqualLeft(arr[::-1])[::-1]]

def solve(N, A):
	firstBiggerLeft = buildFirstBiggerOrEqualLeft(A)
	firstSmallerLeft = buildFirstSmallerOrEqualLeft(A)
	firstBiggerRight = buildFirstBiggerOrEqualRight(A)
	firstSmallerRight = buildFirstSmallerOrEqualRight(A)
	jumps = [[] for i in range(N)]
	for i in range(N):
		j = firstBiggerLeft[i]
		if j != NONE:
			jumps[i].append(j)
		j = firstSmallerLeft[i]
		if j != NONE:
			jumps[i].append(j)
		j = firstBiggerRight[i]
		if j != NONE:
			jumps[j].append(i)
		j = firstSmallerRight[i]
		if j != NONE:
			jumps[j].append(i)
	inf = float('inf')
	dp = [inf for i in range(N)]
	dp[0] = 0
	for i in range(1, N):
		for jump in jumps[i]:
			if DEBUG:
				assert jump < i
				cond1 = all((A[j] > max(A[i], A[jump]) < A[j] for j in range(jump + 1, i)))
				cond2 = all((A[j] < min(A[i], A[jump]) > A[j] for j in range(jump + 1, i)))
				assert cond1 or cond2
			dp[i] = min(dp[i], dp[jump] + 1)
	assert dp[N - 1] != inf
	return dp[N - 1]
DEBUG = False
if DEBUG:
	import random
	random.seed(0)
	for _ in range(1000000):
		N = random.randint(2, 10)
		A = [random.randint(1, 10) for i in range(N)]
		assert len(A) == N
		print('tc', _, N, A)
		ans1 = solve(N, A)
		print(ans1)
	exit()
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(N,) = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = solve(N, A)
print(ans)


from collections import deque

def solve(n, height):
	pos = deque()
	neg = deque()
	dp = [n] * n
	dp[0] = 0
	for i in range(n):
		while len(pos) != 0 and height[pos[-1]] > height[i]:
			dp[i] = min(dp[i], dp[pos[-1]] + 1)
			pos.pop()
		if len(pos) != 0:
			dp[i] = min(dp[i], dp[pos[-1]] + 1)
			if height[pos[-1]] == height[i]:
				pos.pop()
		pos.append(i)
		while len(neg) != 0 and height[neg[-1]] < height[i]:
			dp[i] = min(dp[i], dp[neg[-1]] + 1)
			neg.pop()
		if len(neg) != 0:
			dp[i] = min(dp[i], dp[neg[-1]] + 1)
			if height[neg[-1]] == height[i]:
				neg.pop()
		neg.append(i)
	print(dp[n - 1])
n = int(input())
ar = list(map(int, input().split()))
solve(n, ar)


def find_jumps(heights, iter, jumps):
	greater_stack = []
	lower_stack = []
	for i in iter:
		while greater_stack and heights[i] >= heights[greater_stack[-1]]:
			j = greater_stack.pop()
			jumps[j].append(i)
			jumps[i].append(j)
		while lower_stack and heights[i] <= heights[lower_stack[-1]]:
			j = lower_stack.pop()
			jumps[j].append(i)
			jumps[i].append(j)
		lower_stack.append(i)
		greater_stack.append(i)
n = int(input())
a = list(map(int, input().split()))
jumps = [[] for i in range(0, n)]
find_jumps(a, range(0, n), jumps)
find_jumps(a, reversed(range(0, n)), jumps)
min_dist = [0] * n
for i in reversed(range(0, n - 1)):
	min_dist[i] = min((min_dist[j] + 1 for j in jumps[i] if j > i))
print(min_dist[0])


import sys
from array import array
import typing as Tp

def input():
	return sys.stdin.buffer.readline().decode('utf-8')

def output(*args):
	sys.stdout.buffer.write(('\n'.join(map(str, args)) + '\n').encode('utf-8'))

def main():
	n = int(input())
	a = list(map(int, input().split()))
	next = [[-1] * 2 for _ in range(n)]
	prev = [[-1] * 2 for _ in range(n)]
	for (iter, dp) in ((range(n), next), (range(n - 1, -1, -1), prev)):
		(stack1, stack2) = ([], [])
		for i in iter:
			while stack1 and a[stack1[-1]] <= a[i]:
				dp[stack1.pop()][0] = i
			while stack2 and a[stack2[-1]] >= a[i]:
				dp[stack2.pop()][1] = i
			stack1.append(i)
			stack2.append(i)
	dp = [0] + [10 ** 9] * (n - 1)
	for i in range(n):
		for j in prev[i]:
			if j != -1:
				dp[i] = min(dp[i], dp[j] + 1)
		for j in next[i]:
			if j != -1:
				dp[j] = min(dp[j], dp[i] + 1)
	print(dp[n - 1])
main()


from sys import stdin, stdout

def discrete_centrifugal_jumps(n, h_a):
	jump_a1 = [[] for _ in range(n)]
	jump_a2 = [[] for _ in range(n)]
	st1 = []
	st2 = []
	for i in range(n):
		if not st1 or h_a[i] <= st1[-1][1]:
			st1.append([i, h_a[i]])
		else:
			pre = -1
			while st1 and st1[-1][1] < h_a[i]:
				p = st1.pop()
				if pre != p[1]:
					jump_a1[p[0]].append(i)
				pre = p[1]
			if st1:
				jump_a1[st1[-1][0]].append(i)
			st1.append([i, h_a[i]])
		if not st2 or h_a[i] >= st2[-1][1]:
			st2.append([i, h_a[i]])
		else:
			pre = -1
			while st2 and st2[-1][1] > h_a[i]:
				p = st2.pop()
				if pre != p[1]:
					jump_a2[p[0]].append(i)
				pre = p[1]
			if st2:
				jump_a2[st2[-1][0]].append(i)
			st2.append([i, h_a[i]])
	dp = [2 ** 31 - 1 for _ in range(n)]
	dp[n - 1] = 0
	for i in range(n - 2, -1, -1):
		dp[i] = 1 + dp[i + 1]
		for nxt in jump_a1[i]:
			dp[i] = min(dp[i], 1 + dp[nxt])
		for nxt in jump_a2[i]:
			dp[i] = min(dp[i], 1 + dp[nxt])
	return dp[0]

def dfs(i, jump_a1, jump_a2, n, memo):
	if i == n - 1:
		return 0
	if memo[i] != -1:
		return memo[i]
	res = 2 ** 31 - 1
	for nxt in jump_a1[i]:
		res = min(res, 1 + dfs(nxt, jump_a1, jump_a2, n, memo))
	for nxt in jump_a2[i]:
		res = min(res, 1 + dfs(nxt, jump_a1, jump_a2, n, memo))
	res = min(res, 1 + dfs(i + 1, jump_a1, jump_a2, n, memo))
	memo[i] = res
	return res
n = int(stdin.readline())
h_a = list(map(int, stdin.readline().split()))
k = discrete_centrifugal_jumps(n, h_a)
stdout.write(str(k) + '\n')


import os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
n = int(input())
a = list(map(int, input().split()))
pos = []
neg = []
dp = [n] * n
dp[0] = 0
for i in range(n):
	while pos and a[pos[-1]] > a[i]:
		dp[i] = min(dp[i], dp[pos[-1]] + 1)
		pos.pop()
	if pos:
		dp[i] = min(dp[i], dp[pos[-1]] + 1)
		if a[i] == a[pos[-1]]:
			pos.pop()
	pos.append(i)
	while neg and a[neg[-1]] < a[i]:
		dp[i] = min(dp[i], dp[neg[-1]] + 1)
		neg.pop()
	if neg:
		dp[i] = min(dp[i], dp[neg[-1]] + 1)
		if a[i] == a[neg[-1]]:
			neg.pop()
	neg.append(i)
print(dp[-1])


n = int(input())
a = list(map(int, input().split()))
s1 = [[0, a[0]]]
s2 = [[0, a[0]]]
dp = [float('inf')] * n
dp[0] = 0
for i in range(1, n):
	dp[i] = dp[i - 1] + 1
	while len(s1) > 0 and s1[-1][1] > a[i]:
		(idx, val) = s1.pop()
		dp[i] = min(dp[i], dp[idx] + 1)
	if len(s1) > 0:
		dp[i] = min(dp[i], dp[s1[-1][0]] + 1)
		if s1[-1][1] == a[i]:
			s1.pop()
	s1.append([i, a[i]])
	while len(s2) > 0 and s2[-1][1] < a[i]:
		(idx, val) = s2.pop()
		dp[i] = min(dp[i], dp[idx] + 1)
	if len(s2) > 0:
		dp[i] = min(dp[i], dp[s2[-1][0]] + 1)
		if s2[-1][1] == a[i]:
			s2.pop()
	s2.append([i, a[i]])
print(dp[-1])


import io
import os
import sys
import math
fileno = sys.stdin.fileno()
input = io.BytesIO(os.read(fileno, os.fstat(fileno).st_size)).readline

def solve_slow(N, A):
	ans = [i for i in range(N)]
	for i in range(0, N - 1):
		ans[i + 1] = min(ans[i + 1], ans[i] + 1)
		j = i + 2
		min_height = A[i + 1]
		max_height = A[i + 1]
		while j < N and (max_height < A[i] or min_height > A[i]):
			if max_height < min(A[i], A[j]) or min_height > max(A[i], A[j]):
				ans[j] = min(ans[j], ans[i] + 1)
			if A[j] > max_height:
				max_height = A[j]
			if A[j] < min_height:
				min_height = A[j]
			j += 1
	print(ans)
	return ans[N - 1]

def solve_fast(N, A):
	next = [[i + 1] for i in range(N - 1)]
	big_s = [(A[0], 0)]
	small_s = [(A[0], 0)]
	for i in range(1, N):
		while big_s and big_s[-1][0] < A[i]:
			big_s.pop()
		if big_s:
			(big, big_index) = big_s[-1]
			if big_index + 1 < i:
				next[big_index].append(i)
		while small_s and small_s[-1][0] > A[i]:
			small_s.pop()
		if small_s:
			(small, small_index) = small_s[-1]
			if small_index + 1 < i:
				next[small_index].append(i)
		tpl = (A[i], i)
		big_s.append(tpl)
		small_s.append(tpl)
	big_s = [(A[N - 1], N - 1)]
	small_s = [(A[N - 1], N - 1)]
	for i in range(N - 2, -1, -1):
		while big_s and big_s[-1][0] < A[i]:
			big_s.pop()
		if big_s:
			(big, big_index) = big_s[-1]
			if i + 1 < big_index:
				next[i].append(big_index)
		while small_s and small_s[-1][0] > A[i]:
			small_s.pop()
		if small_s:
			(small, small_index) = small_s[-1]
			if i + 1 < small_index:
				next[i].append(small_index)
		tpl = (A[i], i)
		big_s.append(tpl)
		small_s.append(tpl)
	ans = [i for i in range(N)]
	for i in range(N - 1):
		for j in next[i]:
			ans[j] = min(ans[j], ans[i] + 1)
	return ans[N - 1]
N = int(input())
A = list(map(int, input().split()))
print(solve_fast(N, A))


import os
import sys
from io import BytesIO, IOBase
import threading
from collections import defaultdict, Counter
from math import gcd

def main():
	n = int(input())
	arr = list(map(int, input().split()))
	trans = [[] for i in range(n)]
	mxs = []
	mis = []
	for i in range(n):
		while len(mxs) and mxs[-1][1] < arr[i]:
			mxs.pop()
		if len(mxs):
			trans[mxs[-1][0]].append(i)
		while len(mis) and mis[-1][1] > arr[i]:
			mis.pop()
		if len(mis):
			trans[mis[-1][0]].append(i)
		mxs.append((i, arr[i]))
		mis.append((i, arr[i]))
	mis = []
	mxs = []
	for i in range(n - 1, -1, -1):
		while len(mxs) and mxs[-1][1] < arr[i]:
			mxs.pop()
		if len(mxs):
			trans[i].append(mxs[-1][0])
		while len(mis) and mis[-1][1] > arr[i]:
			mis.pop()
		if len(mis):
			trans[i].append(mis[-1][0])
		mxs.append((i, arr[i]))
		mis.append((i, arr[i]))
	ans = [float('inf')] * n
	ans[0] = 0
	for i in range(n):
		for nxt in trans[i]:
			ans[nxt] = min(ans[nxt], ans[i] + 1)
	print(ans[-1])
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
for i in range(1):
	main()


import sys
import math as mt
input = sys.stdin.readline
t = 1
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	dp = [n] * (n + 1)
	dp[0] = 0
	to = [set() for _ in range(n)]
	stack = []
	for i in range(n):
		while stack and stack[-1][1] < l[i]:
			stack.pop()
		if stack:
			to[i].add(stack[-1][0])
		if stack and stack[-1][1] == l[i]:
			stack.pop()
		stack.append((i, l[i]))
	stack = []
	for i in range(n):
		while stack and stack[-1][1] > l[i]:
			stack.pop()
		if stack:
			to[i].add(stack[-1][0])
		if stack and stack[-1][1] == l[i]:
			stack.pop()
		stack.append((i, l[i]))
	stack = []
	for i in range(n - 1, -1, -1):
		while stack and stack[-1][1] < l[i]:
			stack.pop()
		if stack:
			to[stack[-1][0]].add(i)
		if stack and stack[-1][1] == l[i]:
			stack.pop()
		stack.append((i, l[i]))
	stack = []
	for i in range(n - 1, -1, -1):
		while stack and stack[-1][1] > l[i]:
			stack.pop()
		if stack:
			to[stack[-1][0]].add(i)
		if stack and stack[-1][1] == l[i]:
			stack.pop()
		stack.append((i, l[i]))
	for i in range(1, n):
		for j in to[i]:
			dp[i] = min(dp[i], dp[j] + 1)
	print(dp[n - 1])


import sys
input = sys.stdin.readline
(N,) = map(int, input().split())
X = list(map(int, input().split()))
d = [set() for _ in range(N)]
stack = [(-1, -1)]
for i in range(N):
	while stack and stack[-1][0] > X[i]:
		stack.pop()
	if stack[-1][1] >= 0:
		d[stack[-1][1]].add(i)
	stack.append((X[i], i))
stack = [(10 ** 18, -1)]
for i in range(N):
	while stack and stack[-1][0] < X[i]:
		stack.pop()
	if stack[-1][1] >= 0:
		d[stack[-1][1]].add(i)
	stack.append((X[i], i))
stack = [(-1, N)]
for i in range(N - 1, -1, -1):
	while stack and stack[-1][0] > X[i]:
		stack.pop()
	if stack[-1][1] < N:
		d[i].add(stack[-1][1])
	stack.append((X[i], i))
stack = [(10 ** 18, N)]
for i in range(N - 1, -1, -1):
	while stack and stack[-1][0] < X[i]:
		stack.pop()
	if stack[-1][1] < N:
		d[i].add(stack[-1][1])
	stack.append((X[i], i))
from collections import deque
queue = deque([0])
vs = set([0])
dist = [0] * N
while queue:
	v = queue.popleft()
	for u in d[v]:
		if u in vs:
			continue
		vs.add(u)
		queue.append(u)
		dist[u] = dist[v] + 1
print(dist[-1])


n = int(input())
num = list(map(int, input().split()))
dp = [i for i in range(n)]
dp[0] = 0
higher = []
lower = []
for i in range(n):
	flag = True
	while higher and num[higher[-1]] >= num[i]:
		val = higher.pop()
		dp[i] = min(dp[i], dp[val] + 1)
		flag = False if num[i] == num[val] else True
	if higher and flag:
		dp[i] = min(dp[higher[-1]] + 1, dp[i])
	while lower and num[lower[-1]] <= num[i]:
		val = lower.pop()
		dp[i] = min(dp[i], dp[val] + 1)
		flag = False if num[i] == num[val] else True
	if lower and flag:
		dp[i] = min(dp[lower[-1]] + 1, dp[i])
	higher.append(i)
	lower.append(i)
print(dp[-1])


n = int(input())
h = list(map(int, input().split()))
dp = [0] * n
s = [0]
p = [0]
for i in range(1, n):
	dp[i] = dp[i - 1] + 1
	while len(s) and h[i] >= h[s[-1]]:
		x = s[-1]
		s.pop()
		if h[i] > h[x] and len(s):
			dp[i] = min(dp[i], dp[s[-1]] + 1)
	while len(p) and h[i] <= h[p[-1]]:
		x = p[-1]
		p.pop()
		if h[i] < h[x] and len(p):
			dp[i] = min(dp[i], dp[p[-1]] + 1)
	s.append(i)
	p.append(i)
print(dp[-1])


from collections import deque
import sys
n = int(input())
s = list(map(int, input().split()))
mn = deque()
mx = deque()
p = s + []
i = 0
j = 0
mn.append(i)
mx.append(i)
ans = [sys.maxsize for i in range(n)]
ans[0] = 0
for i in range(1, n):
	while len(mx) > 0 and p[mx[-1]] < p[i]:
		ans[i] = min(ans[i], ans[mx[-1]] + 1)
		index = mx[-1]
		while len(mx) > 0 and p[mx[-1]] == p[index]:
			mx.pop()
	if len(mx) > 0:
		ans[i] = min(ans[i], ans[mx[-1]] + 1)
	mx.append(i)
	while len(mn) > 0 and p[mn[-1]] > p[i]:
		ans[i] = min(ans[i], ans[mn[-1]] + 1)
		index = mn[-1]
		while len(mn) > 0 and p[mn[-1]] == p[index]:
			mn.pop()
	if len(mn) > 0:
		ans[i] = min(ans[i], ans[mn[-1]] + 1)
	mn.append(i)
print(ans[n - 1])


from collections import *
import sys

def ri():
	return int(input())

def rl():
	return list(map(int, input().split()))
n = ri()
h = rl()
g = defaultdict(list)
for rot in range(2):
	stack = []
	for i in range(n):
		while stack and h[stack[-1]] < h[i]:
			g[stack[-1]].append(i)
			stack.pop()
		if stack:
			g[stack[-1]].append(i)
			if h[stack[-1]] == h[i]:
				stack.pop()
		stack.append(i)
	for i in range(n):
		h[i] = -h[i]
dist = [-1] * n
dist[0] = 0
que = [0]
for b in que:
	for j in g[b]:
		if dist[j] == -1:
			que.append(j)
			dist[j] = dist[b] + 1
print(dist[n - 1])


n = int(input())
a = list(map(int, input().split()))
llvisited = [-1 for i in range(n)]
lhvisited = [-1 for i in range(n)]
rlvisited = [-1 for i in range(n)]
rhvisited = [-1 for i in range(n)]
stack = []
for i in range(n):
	while stack and a[i] > stack[-1][0]:
		stack.pop(-1)
	if stack:
		llvisited[i] = stack[-1][1]
	stack.append([a[i], i])
stack = []
for i in range(n):
	while stack and a[i] < stack[-1][0]:
		stack.pop(-1)
	if stack:
		lhvisited[i] = stack[-1][1]
	stack.append([a[i], i])
stack = []
for i in range(n - 1, -1, -1):
	while stack and a[i] > stack[-1][0]:
		stack.pop(-1)
	if stack:
		rlvisited[i] = stack[-1][1]
	stack.append([a[i], i])
stack = []
for i in range(n - 1, -1, -1):
	while stack and a[i] < stack[-1][0]:
		stack.pop(-1)
	if stack:
		rhvisited[i] = stack[-1][1]
	stack.append([a[i], i])
pointers = [[] for i in range(n)]
for i in range(n):
	if llvisited[i] != -1:
		pointers[llvisited[i]].append(i)
	if lhvisited[i] != -1:
		pointers[lhvisited[i]].append(i)
	if rlvisited[i] != -1:
		pointers[i].append(rlvisited[i])
	if rhvisited[i] != -1:
		pointers[i].append(rhvisited[i])
dp = [i for i in range(n)]
for i in range(n):
	for j in pointers[i]:
		dp[j] = min(dp[j], dp[i] + 1)
print(dp[-1])


import sys
read = lambda : sys.stdin.readline().strip()
readi = lambda : map(int, read().split())
from collections import deque
n = int(read())
nums = list(readi())
dp = [float('inf')] * n
dp[0] = 0
incrStk = deque()
decrStk = deque()
for (i, num) in enumerate(nums):
	while incrStk and nums[incrStk[-1]] > num:
		dp[i] = min(dp[i], dp[incrStk.pop()] + 1)
	if incrStk:
		dp[i] = min(dp[i], dp[incrStk[-1]] + 1)
		if nums[incrStk[-1]] == num:
			incrStk.pop()
	incrStk.append(i)
	while decrStk and nums[decrStk[-1]] < num:
		dp[i] = min(dp[i], dp[decrStk.pop()] + 1)
	if decrStk:
		dp[i] = min(dp[i], dp[decrStk[-1]] + 1)
		if nums[decrStk[-1]] == num:
			decrStk.pop()
	decrStk.append(i)
print(dp[-1])


import sys
sys.setrecursionlimit(10 ** 5)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.readline())

def MI():
	return map(int, sys.stdin.readline().split())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def SI():
	return sys.stdin.readline()[:-1]
inf = 10 ** 9
n = II()
aa = LI()
to = [set() for _ in range(n)]
stack = []
for i in range(n):
	while stack and stack[-1][1] < aa[i]:
		stack.pop()
	if stack:
		to[stack[-1][0]].add(i)
	if stack and stack[-1][1] == aa[i]:
		stack.pop()
	stack.append((i, aa[i]))
stack = []
for i in range(n):
	while stack and stack[-1][1] > aa[i]:
		stack.pop()
	if stack:
		to[stack[-1][0]].add(i)
	if stack and stack[-1][1] == aa[i]:
		stack.pop()
	stack.append((i, aa[i]))
stack = []
for i in range(n - 1, -1, -1):
	while stack and stack[-1][1] < aa[i]:
		stack.pop()
	if stack:
		to[i].add(stack[-1][0])
	if stack and stack[-1][1] == aa[i]:
		stack.pop()
	stack.append((i, aa[i]))
stack = []
for i in range(n - 1, -1, -1):
	while stack and stack[-1][1] > aa[i]:
		stack.pop()
	if stack:
		to[i].add(stack[-1][0])
	if stack and stack[-1][1] == aa[i]:
		stack.pop()
	stack.append((i, aa[i]))

def chmin(i, val):
	if val < dp[i]:
		dp[i] = val
dp = [inf] * n
dp[0] = 0
for i in range(n - 1):
	for j in to[i]:
		chmin(j, dp[i] + 1)
print(dp[-1])