Description：

对整个数组进行冒泡排序直到找到一个位置满足前面的最大值小于后面的最小值，冒泡排序每次交换两个数会产生一的贡献，找到一个分割点后两边递归求解，问最后整个数组的总贡献。

$1\le n \le 100000$

Solution：

先分析一下分割点的含义，一个位置能成为分割点一定是前面的数是最终排好序的序列中 $1\sim i$ 的数，后面的是 $i+1\sim n$ ，又发现分割点两边递归冒泡排序相当于整体冒泡排序，因为并不会有元素从一边到另一边，我们可以统计一个 $mx$ 示在最终排好序的数组前 $i$ 个元素中中在原序列下标最大是几，分析一下冒泡排序的性质就会发现 $i$ 和 $i+1$ 之间出现分割点的最早时间是 $mx-i$ ，而一个元素被排好序当且仅当它两边都出现分割点，把这个数累加求和即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

inline int read()

{

	register int res = 0;

	register char c = getchar();

	while(!isdigit(c))c = getchar();

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res;

}

int n;

#define MAXN 100010

struct node

{

	int x,id;

}a[MAXN];

bool cmp_x(node w1,node w2){return (w1.x == w2.x ? w1.id < w2.id : w1.x < w2.x);}

int cnt[MAXN];

int main()

{

	scanf("%d",&n);

	if(n == 1)

	{

		puts("0");

		return 0;

	}

	for(int i = 1;i <= n;++i)

	{

		scanf("%d",&a[i].x);

		a[i].id = i;

	}

	sort(a + 1,a + 1 + n,cmp_x);

	int mx = 0;

	for(int i = 1;i < n;++i)

	{

		mx = max(mx,a[i].id);

		cnt[i] = mx - i;

	}

	long long ans = 0;

	for(int i = 1;i <= n;++i)

	{

		int x = max(cnt[i],cnt[i - 1]);

		if(x == 0)++x;ans += x;

	}

	cout << ans << endl;

	return 0;

}