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.math.BigInteger;
import java.util.*;
import java.io.*;

public class Main {
    static int[]pres,nxts,preg,nxtg,a;
    static int n;
    static void Process(){
        pres= new int[n];
        preg= new int[n];
        Stack<Integer>st= new Stack<>();
        Stack<Integer>st2= new Stack<>();
        for (int i =0;i<n;i++){
            while (!st.isEmpty()&&a[i]>a[st.peek()])
                st.pop();
            while (!st2.isEmpty()&&a[i]<a[st2.peek()])
                st2.pop();
            preg[i]=0;
            pres[i]=0;
            if (!st.isEmpty())
                preg[i]=st.peek();
            if (!st2.isEmpty())
                pres[i]=st2.peek();
            st.push(i);
            st2.push(i);
        }
        nxts= new int[n];
        nxtg= new int[n];
        st= new Stack<>();
        st2= new Stack<>();
        for (int i =n-1;i>=0;i--){
            while (!st.isEmpty()&&a[i]>a[st.peek()])
                st.pop();
            while (!st2.isEmpty()&&a[i]<a[st2.peek()])
                st2.pop();
            nxtg[i]=n-1;
            nxts[i]=n-1;
            if (!st.isEmpty())
                nxtg[i]=st.peek();
            if (!st2.isEmpty())
                nxts[i]=st2.peek();
            st.push(i);
            st2.push(i);
        }
    }
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        PrintWriter pw = new PrintWriter(System.out);
        n = sc.nextInt();
        a= sc.nextIntArr(n);
        Process();
        PriorityQueue<int[]>pqm= new PriorityQueue<>((x,y)->y[0]-x[0]);
        PriorityQueue<int[]>pqs= new PriorityQueue<>((x,y)->y[0]-x[0]);
        pqm.add(new int[]{preg[n-1],n-1});
        pqs.add(new int[]{pres[n-1],n-1});
        int[]dis = new int[n];
        Arrays.fill(dis,n);
        dis[n-1]=0;
        int sz=1;
        while (sz<=n)sz*=2;
        SegmentTree sm= new SegmentTree(sz);
        SegmentTree mx = new SegmentTree(sz);
        sm.update_point(n,0);
        mx.update_point(n,0);
//        System.err.println(Arrays.toString(preg));
//        System.err.println(sm.query(1,n));
        for (int i =n-2;i>=0;i--){
            int cur=n;
//            System.err.println(i+" "+nxts[i]+" "+nxtg[i]);
            cur=Math.min(cur,1+sm.query(i+1,nxts[i]+1));
            cur=Math.min(cur,1+mx.query(i+1,nxtg[i]+1));
            dis[i]=cur;
            sm.update_point(i+1,dis[i]);
            mx.update_point(i+1,dis[i]);
            pqs.add(new int[]{pres[i],i});
            pqm.add(new int[]{preg[i],i});
            while (!pqs.isEmpty()&&pqs.peek()[0]>=i){
                int id=pqs.poll()[1]+1;
                sm.update_point(id,(int)1e9);
            }
            while (!pqm.isEmpty()&&pqm.peek()[0]>=i){
                int id=pqm.poll()[1]+1;
                mx.update_point(id,(int)1e9);
            }
        }
        pw.println(dis[0]);
        pw.close();

    }
    static class SegmentTree {        // 1-based DS, OOP

        int N;            //the number of elements in the array as a power of 2 (i.e. after padding)
        int[] sTree;

        SegmentTree(int in) {
            N = in;
            sTree = new int[N << 1];//no. of nodes = 2*N - 1, we add one to cross out index zero
            Arrays.fill(sTree,(int)1e9);
        }


        void update_point(int index, int val)            // O(log n)
        {
            index += N - 1;
            sTree[index] = val;
            while (index > 1) {
                index >>= 1;
                sTree[index] = Math.min(sTree[index << 1] , sTree[index << 1 | 1]);
            }
        }




        int query(int i, int j) {
            return query(1, 1, N, i, j);
        }

        int query(int node, int b, int e, int i, int j)    // O(log n)
        {
            if (i > e || j < b)
                return (int)1e9;
            if (b >= i && e <= j)
                return sTree[node];
            int mid = b + e >> 1;
            int q1 = query(node << 1, b, mid, i, j);
            int q2 = query(node << 1 | 1, mid + 1, e, i, j);
            return Math.min(q1 , q2);
        }
    }
    static int gcd(int a,int b){
        if (a==0)
            return b;
        return gcd(b%a,a);
    }
    static class Scanner {
        BufferedReader br;
        StringTokenizer st;

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

        public Scanner(FileReader f) {
            br = new BufferedReader(f);
        }

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

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

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

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

        public int[] nextIntArr(int n) throws IOException {
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) {
                arr[i] = Integer.parseInt(next());
            }
            return arr;
        }

    }

}