//為什麼我的 Chrome OS 更新後變成強制繁體了？?

題目要求使用最少的雙端隊列來維護一個單調非降序列

先來看下規律

首先，val 肯定是單調非降的，在相等 val 範圍內的 id 可以 xjb 亂放不影響

其次，在單調可解的 val 範圍內，id 一定是中間小兩邊大（中間是最初維護的，而兩邊是不斷地插入肯定越來越大）

即 id 在某一範圍內是 v 型分布的

因為 val 是單調的，所以對不同的 val 進行分塊管理對應的 id，很顯然最低成立的條件是相同 val（塊）的 id 肯定是緊挨著的，而且是每一個塊逐步往右靠（單調嘛）

如果不可解，那就意味著 id 的分布至少是 vv 型的，即至少多了一個極大值拐點，那麼拐點數 +1 就是使用隊列的數量

所以問題轉換成給定你未管理好的 id，求最少的拐點數

貪心策略是能相同單調性就盡可能相同單調，否則相反單調

（一個錯誤策略是盡可能遞減單調，因為當前遞減的話對應三種不同高度的右下”“塊狀 id 是最優的，然而 GG，原因待查）

/*H E A D*/
struct A{
    int id,val;
}a[maxn];
bool cmp(A a,A b){
    if(a.val!=b.val)return a.val<b.val;
    return a.id<b.id;
}
int main(){
    int n;
    while(~iin(n)){
        rep(i,1,n){
            a[i].val=read();
            a[i].id=i;
        }
        sort(a+1,a+1+n,cmp);
        vector<A> block[maxn];
        int now=0;
        rep(i,1,n){
            if(i==1||a[i].val!=block[now][0].val){
                now++;
                block[now].push_back(a[i]);
            }else{
                block[now].push_back(a[i]);
            }
        }
        int ans=0;
        rep(i,1,now) sort(block[i].begin(),block[i].end(),cmp);//trend=+1
        vector<int> que;
        int trend;
        rep(i,1,now){
            if(i==1){
                for(int j = block[i].size()-1; j >= 0; j--){
                        que.push_back(block[i][j].id);
                }
                trend=-1;
            }else if(trend==-1){
                if(block[i].back().id<que.back()){
                    for(int j = block[i].size()-1; j >= 0; j--){
                        que.push_back(block[i][j].id);
                    }
                    trend=-1;
                }else{
                    for(int j = 0; j < block[i].size(); j++){
                        que.push_back(block[i][j].id);
                    }
                    trend=1;
                }
            }else{
                if(block[i][0].id>que.back()){
                    for(int j = 0; j < block[i].size(); j++){
                        que.push_back(block[i][j].id);
                    }
                    trend=1;
                }
                else{
                     for(int j = block[i].size()-1; j >= 0; j--){
                        que.push_back(block[i][j].id);
                    }
                    trend=-1;
                    ans++;
                }
            }
        }
        println((ans+1));
    }
    return 0;
}