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.
/**
 * author: derrick20
 * created: 9/12/20 1:48 PM
 */
import java.io.*;
import java.util.*;

public class DiscreteJumpsSimple implements Runnable {
    public static void main(String[] args) throws Exception {
        new Thread(null, new DiscreteJumpsSimple(), ": )", 1 << 28).start();
    }

    public void run() {
        FastScanner sc = new FastScanner();
        PrintWriter out = new PrintWriter(System.out);

        int N = sc.nextInt();
        int[] h = sc.nextInts(N);
        int[] dp = new int[N];
        Arrays.fill(dp, N);
        ArrayDeque<Integer>[] extrema = new ArrayDeque[2];
        Arrays.setAll(extrema, i -> new ArrayDeque<>());
        /*
        Restate the condition as:
        Invariant: structure is monotonic increasing
        Consider jth element, and i is the end of the structure
        Let's focus on h[j] being > h[i]:
        Base case: If h[j] <= h[i], (i = j - 1 initially), then we can transition there
        validly only

        Example: [curr = 4] -> 2 3 5
        If h[j] > h[i] (4 > 2), we can transition to this, and also try the next element.
        This next element will also be valid because since all elements between 2 and 3
        are < 2 because of our invariant. They can all be ignored. Eventually we'll run
        into the base case.

        Motivation
        Repeat for minima.
         */
        extrema[0].add(0);
        extrema[1].add(0);
        dp[0] = 0;
        int[] sign = new int[]{1, -1};
        for (int j = 1; j < N; j++) {
            for (int type = 0; type <= 1; type++) {
                while (extrema[type].size() > 0 && sign[type] * h[j] > sign[type] * h[extrema[type].getLast()]) {
                    int i = extrema[type].pollLast();
                    dp[j] = Math.min(dp[j], dp[i] + 1);
                }
                // base case
                if (extrema[type].size() > 0) {
                    int i = extrema[type].getLast();
                    if (h[i] == h[j]) {
                        extrema[type].pollLast();
                        // tricky, future j's can only transition to the last occurrence of a given value
                    }
                    dp[j] = Math.min(dp[j], dp[i] + 1);
                }
                extrema[type].add(j);
            }
        }
        out.println(dp[N - 1]);
        out.close();
    }

    static class FastScanner {
        private int BS = 1 << 16;
        private char NC = (char) 0;
        private byte[] buf = new byte[BS];
        private int bId = 0, size = 0;
        private char c = NC;
        private double cnt = 1;
        private BufferedInputStream in;

        public FastScanner() {
            in = new BufferedInputStream(System.in, BS);
        }

        public FastScanner(String s) {
            try {
                in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
            } catch (Exception e) {
                in = new BufferedInputStream(System.in, BS);
            }
        }

        private char getChar() {
            while (bId == size) {
                try {
                    size = in.read(buf);
                } catch (Exception e) {
                    return NC;
                }
                if (size == -1) return NC;
                bId = 0;
            }
            return (char) buf[bId++];
        }

        public int nextInt() {
            return (int) nextLong();
        }

        public int[] nextInts(int N) {
            int[] res = new int[N];
            for (int i = 0; i < N; i++) {
                res[i] = (int) nextLong();
            }
            return res;
        }

        public long[] nextLongs(int N) {
            long[] res = new long[N];
            for (int i = 0; i < N; i++) {
                res[i] = nextLong();
            }
            return res;
        }

        public long nextLong() {
            cnt = 1;
            boolean neg = false;
            if (c == NC) c = getChar();
            for (; (c < '0' || c > '9'); c = getChar()) {
                if (c == '-') neg = true;
            }
            long res = 0;
            for (; c >= '0' && c <= '9'; c = getChar()) {
                res = (res << 3) + (res << 1) + c - '0';
                cnt *= 10;
            }
            return neg ? -res : res;
        }

        public double nextDouble() {
            double cur = nextLong();
            return c != '.' ? cur : cur + nextLong() / cnt;
        }

        public double[] nextDoubles(int N) {
            double[] res = new double[N];
            for (int i = 0; i < N; i++) {
                res[i] = nextDouble();
            }
            return res;
        }

        public String next() {
            StringBuilder res = new StringBuilder();
            while (c <= 32) c = getChar();
            while (c > 32) {
                res.append(c);
                c = getChar();
            }
            return res.toString();
        }

        public String nextLine() {
            StringBuilder res = new StringBuilder();
            while (c <= 32) c = getChar();
            while (c != '\n') {
                res.append(c);
                c = getChar();
            }
            return res.toString();
        }

        public boolean hasNext() {
            if (c > 32) return true;
            while (true) {
                c = getChar();
                if (c == NC) return false;
                else if (c > 32) return true;
            }
        }
    }
    static void ASSERT(boolean assertion, String message) {
        if (!assertion) throw new AssertionError(message);
    }
    static void ASSERT(boolean assertion) {
        if (!assertion) throw new AssertionError();
    }
}