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.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        solve(in, out);
        out.close();
    }

    static String reverse(String s) {
        return (new StringBuilder(s)).reverse().toString();
    }

    static void sieveOfEratosthenes(int n, int factors[]) 
    { 
        factors[1]=1;
        for(int p = 2; p*p <=n; p++) 
        { 
            if(factors[p] == 0) 
            { 
                factors[p]=p;
                for(int i = p*p; i <= n; i += p) 
                    factors[i] = p; 
            } 
        } 
    }

    static void sort(int ar[]) {
        int n = ar.length;
        ArrayList<Integer> a = new ArrayList<>();
        for (int i = 0; i < n; i++)
            a.add(ar[i]);
        Collections.sort(a);
        for (int i = 0; i < n; i++)
            ar[i] = a.get(i);
    }

    static void sort1(long ar[]) {
        int n = ar.length;
        ArrayList<Long> a = new ArrayList<>();
        for (int i = 0; i < n; i++)
            a.add(ar[i]);
        Collections.sort(a);
        for (int i = 0; i < n; i++)
            ar[i] = a.get(i);
    }

    static long ncr(long n, long r, long mod) {
        if (r == 0)
            return 1;
        long val = ncr(n - 1, r - 1, mod);
        val = (n * val) % mod;
        val = (val * modInverse(r, mod)) % mod;
        return val;
    }

    public static void solve(InputReader sc, PrintWriter pw) {
        int i, j = 0;
        int t = 1;  
        // int t = sc.nextInt();
        u: while (t-- > 0) {
            int n = sc.nextInt();
            long h[] = new long[n];
            for(i=0;i<n;i++)
                h[i] = sc.nextInt();
            int prev_greater[] = new int[n];
            int prev_leq[] = new int[n];
            Stack<Integer> pre_gr = new Stack<>();
            Stack<Integer> pre_leq = new Stack<>();
            int next_greater[] = new int[n];
            int next_leq[] = new int[n];
            Stack<Integer> nex_gr = new Stack<>();
            Stack<Integer> nex_leq = new Stack<>();
            for(i=n-1;i>=0;i--){
                while(pre_gr.size()>0&&h[pre_gr.peek()]<=h[i]){
                    prev_greater[pre_gr.pop()] = i;
                }
                pre_gr.push(i);
            }
            while(pre_gr.size()>0){
                int p = pre_gr.pop();
                prev_greater[p] = -1;
            }
            for(i=n-1;i>=0;i--){
                while(pre_leq.size()>0&&h[pre_leq.peek()]>=h[i]){
                    prev_leq[pre_leq.pop()] = i;
                }
                pre_leq.push(i);
            }
            while(pre_leq.size()>0){
                int p = pre_leq.pop();
                prev_leq[p] = -1;
            }
            for(i=0;i<n;i++){
                while(nex_gr.size()>0&&h[nex_gr.peek()]<=h[i]){
                    next_greater[nex_gr.pop()] = i;
                }
                nex_gr.push(i);
            }
            while(nex_gr.size()>0){
                int p = nex_gr.pop();
                next_greater[p] = -1;
            }
            for(i=0;i<n;i++){
                while(nex_leq.size()>0&&h[nex_leq.peek()]>=h[i]){
                    next_leq[nex_leq.pop()] = i;
                }
                nex_leq.push(i);
            }
            while(nex_leq.size()>0){
                int p = nex_leq.pop();
                next_leq[p] = -1;
            }
            ArrayList<Integer> ar[] = new ArrayList[n];
            for(i=0;i<n;i++){
                ar[i] = new ArrayList<>();
            }
            for(i=0;i<n;i++){
                if(next_greater[i]!=-1){
                    ar[i].add(next_greater[i]);
                }
                if(next_leq[i]!=-1){
                    ar[i].add(next_leq[i]);
                }
                if(prev_greater[i]!=-1){
                    ar[prev_greater[i]].add(i);
                }
                if(prev_leq[i]!=-1){
                    ar[prev_leq[i]].add(i);
                }
            }
            int ans[] = new int[n];
            ans[n-1] = 0;
            for(i=n-2;i>=0;i--){
                ans[i] = ans[i+1]+1;
                for(int k:ar[i]){
                    ans[i] = Math.min(ans[i],ans[k]+1);
                }
            }
            // for(i=0;i<n;i++){
            //     pw.println(prev_greater[i] + " " + prev_leq[i] + " " + ans[i]); 
            // }
            pw.println(ans[0]);
        }
    }


    static class Pair implements Comparable<Pair> {
        int a;
        int b;
        // int c;
        
        Pair(int a, int b) {
            this.a = a;
            this.b = b;
        }
 
        public int compareTo(Pair p) {
            if(a!=p.a)
                return p.a-a;
            return b-p.b;
        }
    }

    static boolean isPrime(long n) {
        if (n <= 1)
            return false;
        if (n <= 3)
            return true;
        if (n % 2 == 0 || n % 3 == 0)
            return false;
        for (int i = 5; i * i <= n; i = i + 6)
            if (n % i == 0 || n % (i + 2) == 0)
                return false;
        return true;
    }

    static long gcd(long a, long b) {
        if (b == 0)
            return a;
        return gcd(b, a % b);
    }

    static long fast_pow(long base, long n, long M) {
        if (n == 0)
            return 1;
        if (n == 1)
            return base % M;
        long halfn = fast_pow(base, n / 2, M);
        if (n % 2 == 0)
            return (halfn * halfn) % M;
        else
            return (((halfn * halfn) % M) * base) % M;
    }

    static long modInverse(long n, long M) {
        return fast_pow(n, M - 2, M);
    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 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());
        }
    }
}

