0x10:双端队列
考虑最终有序序列是由若干个双端队列合并得来,先将序列排序.
考虑双端队列中的下标是单谷的,问题转化为最终有序序列最少的单谷段数.
这就只需要记录一下上升还是下降,然后上升转为下降时更新段数即可.

但是可能存在相同的元素,而相同的元素在排序后的序列中的位置是任意的,这需要一些处理.
考虑排序后去重时记录每个值的最大和最小下标.
为什么要这样?因为这些下标可以构成一个序列,也可以构成几个单谷段,但后者显然不优.
于是,只记录最大最小下标就记录了这个序列.然后求单谷段的时候,能插入就整个插入,否则转换递增/递减情况.

可见代码

//Wan Hong 2.2
//notebook
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
typedef long long ll;
typedef std::pair<ll,ll> pll;
typedef std::string str;
#define INF (1ll<<58)
ll read()
{
    ll x=0,f=1;
    char c;
    do
    {
        c=getchar();
        if(c=='-')f=-1;
    }while(c<'0'||c>'9');
    do
    {
        x=x*10+c-'0';
        c=getchar();
    }while(c>='0'&&c<='9');
    return f*x;
}
ll min(ll a,ll b)
{
    return a<b?a:b;
}
ll max(ll a,ll b)
{
    return a>b?a:b;
}
bool umin(ll &a,ll b)
{
    if(b<a)return a=b,1;
    return 0;
}
bool umax(ll &a,ll b)
{
    if(b>a)return a=b,1;
    return 0;
}
/**********/
#define MAXN 200011
#define v first
#define num second
pll a[MAXN];
ll minv[MAXN],maxv[MAXN];
int main()
{
    ll n=read();
    for(ll i=1;i<=n;++i)
    {
        a[i].v=read();
        a[i].num=i;
    }
    std::sort(a+1,a+n+1);
    ll cnt=0;
    for(ll i=1;i<=n;++i)
    {
        if(i==1||a[i].v!=a[i-1].v)
        {
            ++cnt;
            maxv[cnt]=minv[cnt]=a[i].num;
        }
        else
        {
            umax(maxv[cnt],a[i].num);
            umin(minv[cnt],a[i].num);
        }
    }
    bool p=1;
    ll ans=1,now=INF;
    for(ll i=1;i<=cnt;++i)
    {
        if(p)
        {
            if(maxv[i]<=now)now=minv[i];
            else p=0,now=maxv[i];
        }
        else
        {
            if(minv[i]>=now)now=maxv[i];
            else p=1,now=minv[i],++ans;
        }
    }
    printf("%lld",ans);
    return 0;
}