题意

自己看

题解

这题想了很久
首先，第一步，你要知道冒泡一次序列会变成什么东西
显然地，对于一个数，如果前面有比他大的，那么他就会往前面倒推一步
否则，就会往后移，移到第一个比他大的那个数的前面

然后想通了这个以后，我就怒想了一波解法。。然后什么都没想到。。
猜了一手逆序对相关，发现毫无卵用

膜了题解

题解考虑的是对于每一个数他会被算多少次，也就是他递归的层数
这个我也想过，但是我完全没有思路啊TAT
然后一个数，他的递归层数是多少呢？
显然地，就是剩下他一个的时候
也就是他左边的出现了分隔符，右边也出现了分隔符
于是，问题就转化为，某一个分隔符出现的时间
然后一个点的答案就是两个分隔符取max
考虑一个数i前面的分隔符怎么得到
其实就是所有比$i-1$小的数，位置的最大值减去$i-1$
至于为什么，你结合一下我上文说的

显然地，对于一个数，如果前面有比他大的，那么他就会往前面倒推一步

来想一下就可以想出来了
分隔符的出现，只需要把前面i-1个数移到前面去就可以了，并不需要顺序

于是这题就做完啦！
最后，要注意一下有数一样的情况
一开始看成了保证数都相同而WA了很多发

CODE:

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
typedef long long LL;
const LL N=100005;
LL n;
struct qq {LL x,id; }s[N];
LL a[N];
LL f[N];//这个数字在哪里 
LL g[N];
bool cmp (qq x,qq y){
   return x.x==y.x?x.id<y.id:x.x<y.x;}
int main()
{scanf("%lld",&n);if (n==1){printf("0\n");return 0;}for (LL u=1;u<=n;u++){scanf("%lld",&s[u].x);s[u].id=u;}sort(s+1,s+1+n,cmp);for (LL u=1;u<=n;u++)       {a[s[u].id]=u;f[u]=s[u].id;}/*for (LL u=1;u<=n;u++) printf("%lld ",a[u]);printf("\n");for (LL u=1;u<=n;u++) printf("%lld ",f[u]);printf("\n");*/LL ans=0;LL mx=0;//当前的最大值是什么 for (LL u=1;u<=n;u++)   {g[u]=max(1LL,mx-u+1);mx=max(mx,f[u]);}//for (LL u=1;u<=n;u++) printf("%lld ",g[u]); g[n+1]=1;for (LL u=1;u<=n;u++)ans=ans+max(g[u],g[u+1]);printf("%lld\n",ans);return 0;
}