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/9/20 6:36 PM
 */
import java.io.*;
import java.util.*;

public class DiscreteCentrifugalJumps implements Runnable {
    public static void main(String[] args) throws Exception {
        new Thread(null, new DiscreteCentrifugalJumps(), ": )", 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);
        ArrayDeque<Integer> incrLeft = new ArrayDeque<>();
        ArrayDeque<Integer> decrLeft = new ArrayDeque<>();
        ArrayDeque<Integer> incrRight = new ArrayDeque<>();
        ArrayDeque<Integer> decrRight = new ArrayDeque<>();
        /*
        We can visualize any pair of points i, j that are reachable by compressing all the
        points from [i, j] into a vertical line.

        Consider the perspective from each point, and amazingly one of them allows us
        to be able to ask a simple question to know who we can jump to.
        4 cases:
            0 = h[i] <= h[j]:
                i, j are bottom of stack:
                    i is directly below j. Key observation: i is the first
                    pos to the left that's smaller than j.
            1 = h[i] >= h[j]:
                i, j are top of stack:
                    i is directly above j. i is first pos to the left greater
                    than j.

            2 = h[i] >= h[j]:
                i, j are bottom of stack:
                    j is directly below i. j is the first pos to the right
                    smaller than i.

            3 = h[i] <= h[j]
                i, j are top of stack:
                    j is directly above i. j is first pos to the right
                    greater than i.
        It makes more sense to think of these as edges on a graph, need all edges to be
        added before we can properly find a shortest path
        CAN'T GO BACKWARDS!
         */

        HashSet<Integer>[] edges = new HashSet[N];
        Arrays.setAll(edges, i -> new HashSet<>());
        for (int i = 0; i < N; i++) {
            while (incrLeft.size() > 0 && h[i] < h[incrLeft.getLast()]) {
                incrLeft.pollLast();
            }
            // first thing left that's smallerR
            if (incrLeft.size() > 0) {
                int j = incrLeft.getLast();
//                edges[i].add(j);
                edges[j].add(i);
            }
            incrLeft.add(i);
            while (decrLeft.size() > 0 && h[i] > h[decrLeft.getLast()]) {
                decrLeft.pollLast();
            }
            // first thing left that's bigger
            if (decrLeft.size() > 0) {
                int j = decrLeft.getLast();
//                edges[i].add(j);
                edges[j].add(i);
            }
            decrLeft.add(i);
        }

        for (int i = N - 1; i >= 0; i--) {
            // i guess it's increasing from right to left, which is decreasing technically
            while (incrRight.size() > 0 && h[i] < h[incrRight.getLast()]) {
                incrRight.pollLast();
            }
            // first thing right that's smaller
            if (incrRight.size() > 0) {
                int j = incrRight.getLast();
                edges[i].add(j);
//                edges[j].add(i);
            }
            incrRight.add(i);
            while (decrRight.size() > 0 && h[i] > h[decrRight.getLast()]) {
                decrRight.pollLast();
            }
            // first thing right that's greater
            if (decrRight.size() > 0) {
                int j = decrRight.getLast();
                edges[i].add(j);
//                edges[j].add(i);
            }
            decrRight.add(i);
        }

//        for (int i = 0; i < N; i++) {
//            System.out.println(edges[i]);
//        }
        /*
10
1 5 5 5 6 4 5 5 5 7
backwards gives 3, correct is 5
         */
        ArrayDeque<Integer> q = new ArrayDeque<>();
        int[] dist = new int[N];
        Arrays.fill(dist, -1);
        q.add(0);
        dist[0] = 0;
        while (q.size() > 0) {
            int curr = q.pollFirst();
//            System.out.println("Visiting " + curr);
            for (int adj : edges[curr]) {
                if (adj != -1 && dist[adj] == -1) {
                    q.add(adj);
                    dist[adj] = dist[curr] + 1;
                }
            }
        }
//        System.out.println(Arrays.toString(dist));
        out.println(dist[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();
    }
}