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.*;
public class Dv2 { //AC :) 

	public static void main(String[] args) {
		FastScanner sc = new FastScanner();
		int n = sc.nextInt();
		int[] arr = new int[n];
		for(int i = 0; i < n; i++) {
			arr[i] = sc.nextInt();
		}
		int[] upvals = new int[n];
		int[] dnvals = new int[n];
		Arrays.fill(upvals, n+1);
		Arrays.fill(dnvals, n+1);
		int[] dp = new int[n];
		Arrays.fill(dp, n+1);
		dp[0] = upvals[0] = dnvals[0] = 0;
		SegmentTree stup = new SegmentTree(upvals);
		SegmentTree stdn = new SegmentTree(dnvals);
		TreeMap<Integer, Integer> upset = new TreeMap<>();
		upset.put(arr[0], 0);
		TreeMap<Integer, Integer> dnset = new TreeMap<>(Collections.reverseOrder());
		dnset.put(arr[0], 0);
		for(int i = 1; i < n; i++) {
			if(arr[i] == arr[i-1]) dp[i] = dp[i-1] + 1;
			else if(arr[i] > arr[i-1]) {
				Integer a = dnset.floorKey(arr[i]);
				if(a == null) dp[i] = stdn.rmq(0, n-1) + 1;
				else dp[i] = stdn.rmq(dnset.get(a), n-1) + 1;
			}
			else {
				Integer a = upset.floorKey(arr[i]);
				if(a == null) dp[i] = stup.rmq(0, n-1) + 1;
				else dp[i] = stup.rmq(upset.get(a), n-1) + 1;
			}
			
			while(!upset.isEmpty() && upset.lastKey() >= arr[i]) {
				Integer lastk = upset.lastKey();
				stup.update_point(upset.get(lastk), n+1);
				upset.pollLastEntry(); 
			}
			stup.update_point(i, dp[i]);
			upset.put(arr[i], i);
			while(!dnset.isEmpty() && dnset.lastKey() <= arr[i]) {
				Integer lastk = dnset.lastKey();
				stdn.update_point(dnset.get(lastk), n+1);
				dnset.pollLastEntry();
			}
			stdn.update_point(i, dp[i]);
			dnset.put(arr[i], i);
		}
//		System.out.println(Arrays.toString(dp));
		System.out.println(dp[n-1]);
	}
	
	static class SegmentTree {
		private int[] st; private int[] A;
		private int n;
		private int left (int p) { return p << 1; }
		private int right(int p) { return (p << 1) + 1; }
		
		static int neutral = Integer.MAX_VALUE;					//MIN
		static int op(int x, int y) { return Math.min(x, y); }
//		static int neutral = Integer.MIN_VALUE;					//MAX
//		static int op(int x, int y) { return Math.max(x, y); }
//		static int neutral = 0;									//SUM
//		static int op(int x, int y) { return x + y; }

		private void build(int p, int L, int R) {
			if (L == R)
				st[p] = A[L];
			else {
				build(left(p) , L              , (L + R) / 2);
				build(right(p), (L + R) / 2 + 1, R          );
				int v1 = st[left(p)], v2 = st[right(p)];
				st[p] = op(v1, v2);
			} }

		private int rmq(int p, int L, int R, int i, int j) {
			if (i >  R || j <  L) return neutral;
			if (L >= i && R <= j) return st[p];

			int v1 = rmq(left(p) , L              , (L+R) / 2, i, j);
			int v2 = rmq(right(p), (L+R) / 2 + 1, R          , i, j);

			return op(v1, v2);
		}

		private int update_point(int p, int L, int R, int idx, int new_value) {
			int i = idx, j = idx;
			if (i > R || j < L)
				return st[p];

			if (L == i && R == j) {
				A[i] = new_value;
				return st[p] = A[L];											// += IF DELTA
			}

			int v1, v2;
			v1 = update_point(left(p) , L              , (L + R) / 2, idx, new_value);
			v2 = update_point(right(p), (L + R) / 2 + 1, R          , idx, new_value);

			return st[p] = op(v1, v2);
		}

		public SegmentTree(int[] _A) {
			A = _A; n = A.length;
			st = new int[4 * n];
			for (int i = 0; i < 4 * n; i++) st[i] = 0;
			build(1, 0, n - 1);
		}

		public int rmq(int i, int j) { return rmq(1, 0, n - 1, i, j); }

		public int update_point(int idx, int new_value) {
			return update_point(1, 0, n - 1, idx, new_value); }
		
		public String toString() {
			return Arrays.toString(A);
		}
	}
	
	
	static class FastScanner {
        public BufferedReader reader;
        public StringTokenizer tokenizer;
        public FastScanner() {
            reader = new BufferedReader(new InputStreamReader(System.in), 32768);
            tokenizer = null;
        }
        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }
        public int nextInt() {
            return Integer.parseInt(next());
        }
        public long nextLong() {
        	return Long.parseLong(next());
        }
        public double nextDouble() {
        	return Double.parseDouble(next());
        }
        public String nextLine() {
        	try {
        		return reader.readLine();
        	} catch(IOException e) {
        		throw new RuntimeException(e);
        	}
        }
    }

}
