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.*;
import java.math.*;
public class D669{
    public static int bfs(HashSet<Integer> adj[],int n){
        boolean vis[]=new boolean[n+1];
        int i;
        vis[1]=true;
        Queue<Integer> q=new LinkedList<>();
        q.add(1);
        int dist[]=new int[n+1];
        dist[1]=0;
        while(!q.isEmpty()){
            int v=q.poll();
            for(int x:adj[v]){
                if(!vis[x]){
                    vis[x]=true;
                    dist[x]=dist[v]+1;
                    q.add(x);
                    if(x==n)
                        return dist[x];
                }
            }
        }
        return -1;
    }
    static class pair { 
        int val, ind;
        public pair(int a,int b){
            val=a;
            ind=b;
        }
    }
	public static void main(String args[]){
		FastReader sc = new FastReader();
		StringBuilder sb=new StringBuilder();
		int t,i,n;
		t=1;
		while(t-->0){
            n=sc.nextInt();
            int a[]=new int[n];
            HashSet<Integer> adj[]=new HashSet[n+1];
            for(i=1;i<=n;i++){
                adj[i]=new HashSet<>();
            }
            for(i=0;i<n;i++){
                a[i]=sc.nextInt();
            }
            int nge[]=new int[n];
            int nse[]=new int[n];
            Stack<pair> st=new Stack<pair>();
            st.push(new pair(a[0],0));
            pair ele;
            //next greater element
            for(i=1;i<n;i++){
                if(!st.isEmpty()){
                    ele=st.pop();
                    while(ele.val<=a[i]){
                        nge[ele.ind]=i+1;
                        if(st.isEmpty())
                            break;
                        ele=st.pop();
                    }
                    if(ele.val>a[i])
                        st.push(ele);
                }
                st.push(new pair(a[i],i));
            }
            while(!st.isEmpty()){
                ele=st.pop();
                nge[ele.ind]=-1;
            }
            st.clear();
            st.push(new pair(a[0],0));
            // next smaller element
            for(i=1;i<n;i++){
                if(!st.isEmpty()){
                    ele=st.pop();
                    while(a[i]<=ele.val){
                        nse[ele.ind]=i+1;
                        if(st.isEmpty())
                            break;
                        ele=st.pop();
                    }
                    if(a[i]>ele.val)
                        st.push(ele);
                }
                st.push(new pair(a[i],i));
            }
            while(!st.isEmpty()){
                ele=st.pop();
                nse[ele.ind]=-1;
            }
            st.clear();
            int pge[]=new int[n];
            int pse[]=new int[n];
            pge[0]=-1;
            ele = new pair(a[0],0);
            st.push(ele);
            for(i=1;i<n;i++){
                while(!st.isEmpty() && st.peek().val<a[i])
                    st.pop();
                if(st.isEmpty())
                    pge[i]=-1;
                else {
                    pge[i]=st.peek().ind+1;
                }
                st.push(new pair(a[i],i));
            }
            pse[0]=-1;
            ele = new pair(a[0],0);
            st.push(ele);
            for(i=1;i<n;i++){
                while(!st.isEmpty() && st.peek().val>a[i])
                    st.pop();
                if(st.isEmpty()){
                    pse[i]=-1;
                }
                else 
                    pse[i]=st.peek().ind+1;
                st.push(new pair(a[i],i));
            }
            
            for(i=0;i<n;i++){
                if(nge[i]>0){
                    adj[i+1].add(nge[i]);
                    //out.println(i+1+ " "+ nge[i]);
                }
                if(nse[i]>0){
                    adj[i+1].add(nse[i]);
                    //out.println(i+1+ " "+ nse[i]);
                }
                if(pse[i]>0){
                    adj[pse[i]].add(i+1);
                    //out.println(i+1+ " "+ pse[i]);
                }
                if(pge[i]>0){
                    adj[pge[i]].add(i+1);
                    //out.println(i+1+ " "+ pge[i]);
                }
            }

            int ans=bfs(adj,n);
            sb.append(ans).append('\n');
		}
		sb.deleteCharAt(sb.length()-1);
		out.println(sb);
	}

	static PrintWriter out;
	static class FastReader{
		BufferedReader br;
		StringTokenizer st;
		public FastReader(){
			br=new BufferedReader(new InputStreamReader(System.in));
			out=new PrintWriter(System.out,true);
		}
		String next(){
			while(st==null || !st.hasMoreElements()){
				try{
					st= new StringTokenizer(br.readLine());
				}
				catch (IOException e){
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}
		int nextInt(){
			return Integer.parseInt(next());
		}
		long nextLong(){
			return Long.parseLong(next());
		}
		double nextDouble(){
			return Double.parseDouble(next());
		}
		String nextLine(){
			String str = "";
			try{
				str=br.readLine();
			}
			catch(IOException e){
				e.printStackTrace();
			}
			return str;
		}
	}

	public static boolean isPrime(int n) {
		if(n<2) return false;
		for(int i=2;i<=(int)Math.sqrt(n);i++) {
			if(n%i==0) return false;
		}
		return true;
	}

	public static void print(int a[],int l,int r){
		int i;
		for(i=l;i<=r;i++)
			out.print(a[i]+" ");
		out.println();
	}

	public static long fastexpo(long x, long y, long p){
		long res=1;
		while(y > 0){
			if((y & 1)==1)
				res= ((res%p)*(x%p))%p;
			y= y >> 1;			
			x = ((x%p)*(x%p))%p;
		}
		return res;
	}

	public static boolean[] sieve (int n) {
		boolean primes[]=new boolean[n+1];
		Arrays.fill(primes,true);
		primes[0]=primes[1]=false;
		for(int i=2;i*i<=n;i++){
			if(primes[i]){
				for(int j=i*i;j<=n;j+=i)
					primes[j]=false;
			}
		}
		return primes;
	}

	public static long gcd(long a,long b){
        return (BigInteger.valueOf(a).gcd(BigInteger.valueOf(b))).longValue();
    }

    public static void merge(long a[],int l,int m,int r){
        int n1,n2,i,j,k;
        n1=m-l+1;
        n2=r-m;

        long L[]=new long[n1];
        long R[]=new long[n2];

        for(i=0;i<n1;i++)
            L[i]=a[l+i];
        for(j=0;j<n2;j++)
            R[j]=a[m+1+j];

        i=0;j=0;

        k=l;
        while(i<n1&&j<n2){
            if(L[i]<=R[j]){
                a[k]=L[i];
                i++;
            }
            else{
                a[k]=R[j];
                j++;
            }
            k++;
        }

        while(i<n1){
            a[k]=L[i];
            i++;
            k++;
        }
        while(j<n2){
            a[k]=R[j];
            j++;
            k++;
        }
    }
    public static void sort(long a[],int l,int r){
        int m;
        if(l<r){
            m=(l+r)/2;
            sort(a,l,m);
            sort(a,m+1,r);
            merge(a,l,m,r);
        }
    }
}

