达达现在碰到了一个棘手的问题，有 N 个整数需要排序。

达达手头能用的工具就是若干个双端队列。

她从 1 到 N 需要依次处理这 N 个数，对于每个数，达达能做以下两件事：

1．新建一个双端队列，并将当前数作为这个队列中的唯一的数；

2．将当前数放入已有的队列的头之前或者尾之后。

对所有的数处理完成之后，达达将这些队列按一定的顺序连接起来后就可以得到一个非降的序列。

请你求出最少需要多少个双端序列。

输入格式
第一行输入整数 N，代表整数的个数。

接下来 N 行，每行包括一个整数 Di，代表所需处理的整数。

输出格式
输出一个整数，代表最少需要的双端队列数。

数据范围
1≤N≤200000

输入样例：

6
3
6
0
9
6
3

输出样例：

2

参考答案

#include <bits/stdc++.h>
using namespace std;
const int N=200100;
#define pii pair<int,int>
#define fir(i,a,b) for(int i=a;i<=b;i++)
pii a[N<<1];
int cmp(pii a,pii b)
{
    return a.first==b.first ? a.second<b.second : a.first>b.first;;
}
int n,h,b,mx[N],mi[N],cnt,ans;
int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    fir(i,1,n)
        cin>>a[i].first,a[i].second=i;//first为值,second为下标
    sort(a+1,a+1+n,cmp);
    fir(i,1,n)
        if (a[i].first!=a[i-1].first || i==1)//缩点
        {
            mx[cnt]=a[i-1].second;
            mi[++cnt]=a[i].second;
        }
    mx[cnt]=a[n].second;
    b=true;
    h=1<<30;
    fir(i,1,cnt)
        if (!b)
        {
            if (h>mx[i])
                h=mi[i];
            else
                h=mx[i],b=true;//单调性开始变化
        }
        else
        {
            if (h<mi[i])
                h=mx[i];
            else
                h=mi[i],b=false,ans++;//单调性开始变化,同时记录值,因为当前已经抵达单谷.
        }
    cout<<ans;
    return 0;
}