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}, …, h_{j - 1}) < min(h_i, h_j) 
  * max(h_i, h_j) < min(h_{i + 1}, …, 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 ≤ n ≤ 3 ⋅ 10^5) — total amount of skyscrapers.

The second line contains n integers h_1, h_2, …, h_n (1 ≤ h_i ≤ 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 → 2 → 4 → 5.

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

Sequence of jumps in the fourth testcase: 1 → 3 → 5.
import java.util.*;
import java.io.*;
import java.lang.reflect.Array;
import java.math.BigInteger;

public class tr7 {
	static PrintWriter out;
	static StringBuilder sb;
	static int mod = 1000000007;
	static long inf = (long) 1e14;
	static int n;
	static ArrayList<Integer>[] ad;
	static int[][] memo;
	static boolean f;
	static boolean vis[];
	static int[] a;

	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		out = new PrintWriter(System.out);
		n = sc.nextInt();

		a = sc.nextArrInt(n);
		int[] dp = new int[n];
		int[] rmin = new int[n];
		int[] rmax = new int[n];
		Arrays.fill(rmin, n);
		Arrays.fill(rmax, n);
		Stack<Integer> s = new Stack<>();
		for (int i = n - 1; i >= 0; i--) {
			while (!s.isEmpty() && a[s.peek()] < a[i]) {
				s.pop();
			}
			if (!s.isEmpty())
				rmin[i] = s.peek();
			s.add(i);
		}
		s = new Stack<>();
		for (int i = n - 1; i >= 0; i--) {
			while (!s.isEmpty() && a[s.peek()] > a[i]) {
				s.pop();
			}
			if (!s.isEmpty())
				rmax[i] = s.peek();
			s.add(i);
		}
		ad = new ArrayList[n];
		for (int i = 0; i < n; i++)
			ad[i] = new ArrayList<>();
		dp = new int[n];
		Arrays.fill(dp, 1000000);
		dp[n - 1] = 0;
		int[] lmin = new int[n];
		int[] lmax = new int[n];
		Arrays.fill(lmin, -1);
		Arrays.fill(lmax, -1);
		s.clear();
		for (int i = 0; i < n; i++) {
			while (!s.isEmpty() && a[s.peek()] < a[i]) {
				s.pop();
			}
			if (!s.isEmpty())
				lmin[i] = s.peek();
			s.add(i);
		}
		s.clear();
		for (int i = 0; i < n; i++) {
			while (!s.isEmpty() && a[s.peek()] > a[i]) {
				s.pop();
			}
			if (!s.isEmpty())
				lmax[i] = s.peek();
			s.add(i);
		}
		for (int i = 0; i < n; i++) {
			if (lmax[i] != -1)
				ad[lmax[i]].add(i);
			if (lmin[i] != -1)
				ad[lmin[i]].add(i);
		}
		Arrays.fill(dp, 1000000);
		dp[n - 1] = 0;
		for (int i = n - 2; i >= 0; i--) {
			dp[i] = Math.min(dp[i], 1 + dp[i + 1]);
			if (a[i] > a[i + 1]) {
				if (rmin[i] != n)
					dp[i] = Math.min(dp[i], 1 + dp[rmin[i]]);
			} else if (a[i] < a[i + 1]) {
				if (rmax[i] != n)
					dp[i] = Math.min(dp[i], 1 + dp[rmax[i]]);
			}
			for (int j : ad[i])
				dp[i] = Math.min(dp[i], dp[j] + 1);
		}
		System.out.println(dp[0]);
		out.close();
	}

	public static class SparseTableMin {

		int A[], SpT[][];

		SparseTableMin(int[] A) {
			int n = A.length;
			this.A = A;
			int k = (int) Math.floor(Math.log(n) / Math.log(2)) + 1;
			SpT = new int[n][k];

			for (int i = 0; i < n; i++)
				SpT[i][0] = i; // RMQ of sub array starting at index i and of length 2^0=1

			// overall time complexity = O(n log n)
			for (int j = 1; (1 << j) <= n; j++)
				for (int i = 0; i + (1 << j) - 1 < n; i++)
					if (A[SpT[i][j - 1]] < A[SpT[i + (1 << (j - 1))][j - 1]])
						SpT[i][j] = SpT[i][j - 1]; // start at index i of length 2^(j-1)
					else // start at index i+2^(j-1) of length 2^(j-1)
						SpT[i][j] = SpT[i + (1 << (j - 1))][j - 1];
		}

		int query(int i, int j) {

			int k = (int) Math.floor(Math.log(j - i + 1) / Math.log(2)); // 2^k <= (j-i+1)

			if (A[SpT[i][k]] <= A[SpT[j - (1 << k) + 1][k]])
				return SpT[i][k];
			else
				return SpT[j - (1 << k) + 1][k];
		}
	}

	public static class SparseTableMax {

		int A[], SpT[][];

		SparseTableMax(int[] A) {
			int n = A.length;
			this.A = A;
			int k = (int) Math.floor(Math.log(n) / Math.log(2)) + 1;
			SpT = new int[n][k];

			for (int i = 0; i < n; i++)
				SpT[i][0] = i; // RMQ of sub array starting at index i and of length 2^0=1

			// overall time complexity = O(n log n)
			for (int j = 1; (1 << j) <= n; j++)
				for (int i = 0; i + (1 << j) - 1 < n; i++)
					if (A[SpT[i][j - 1]] > A[SpT[i + (1 << (j - 1))][j - 1]])
						SpT[i][j] = SpT[i][j - 1]; // start at index i of length 2^(j-1)
					else // start at index i+2^(j-1) of length 2^(j-1)
						SpT[i][j] = SpT[i + (1 << (j - 1))][j - 1];
		}

		int query(int i, int j) {

			int k = (int) Math.floor(Math.log(j - i + 1) / Math.log(2)); // 2^k <= (j-i+1)
			// System.out.println(i + " " + j + " " + k);
			if (A[SpT[i][k]] >= A[SpT[j - (1 << k) + 1][k]])
				return SpT[i][k];
			else
				return SpT[j - (1 << k) + 1][k];
		}
	}

	static class Scanner {
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream system) {
			br = new BufferedReader(new InputStreamReader(system));
		}

		public Scanner(String file) throws Exception {
			br = new BufferedReader(new FileReader(file));
		}

		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		public String nextLine() throws IOException {
			return br.readLine();
		}

		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}

		public double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}

		public char nextChar() throws IOException {
			return next().charAt(0);
		}

		public Long nextLong() throws IOException {
			return Long.parseLong(next());
		}

		public int[] nextArrInt(int n) throws IOException {
			int[] a = new int[n];
			for (int i = 0; i < n; i++)
				a[i] = nextInt();
			return a;
		}

		public long[] nextArrLong(int n) throws IOException {
			long[] a = new long[n];
			for (int i = 0; i < n; i++)
				a[i] = nextLong();
			return a;
		}

		public boolean ready() throws IOException {
			return br.ready();
		}

		public void waitForInput() throws InterruptedException {
			Thread.sleep(3000);
		}
	}
}