分享一个今天打比赛想出猎奇的做法。

求出了每个分隔点出现的时间，每个点的贡献就是两边分割点出现时间的较大值。

出现分隔点当且仅当前前 $i$ 小的数全部在分隔点前。冒泡过后前个数中最靠右的数一定会向左移，所以时间就是 $r-i$。

先全部排序，从左往右求出现时间，同时用第 $i$ 小的元素的初始位置维护当前最靠右的位置。最后求出答案。

#include<bits/stdc++.h>
using namespace std;
struct Q{
    long long x,id;
}a[100005];
bool cmp(Q x,Q y){
    if(x.x==y.x) return x.id<y.id;
    return x.x<y.x;
}
long long n,res[100005],ms,ans;
int main(){
	cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i].x;
        a[i].id=i;
    }
    
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<n;i++){
        ms=max(ms,a[i].id);
        res[i]=ms-i;
    }
    long long now=1;
    for(int i=1;i<=n;i++){
now=1;
        if(i>=1) now=max(now,res[i-1]);
        if(i<n) now=max(now,res[i]);
        ans+=now;
    }
    cout<<ans<<endl;
}