Description：

双向冒泡排序，问你需要跑几趟。

$1\le n \le 100000$

Solution：

设 $m[i]$ 表示序列前 $i$ 个数中不在 $1\sim i$ 中的数的个数，发现每次双向冒泡排序只会将 $i$ 之前的和 $i$ 之后的一对数互换，所以 $m[i]$ 的最大值就是答案， $m[i]$ 可以用树状数组维护。注意已经排好序的也要走一遍。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n;

#define MAXN 100010

struct node

{

	int x,id;

}s[MAXN];

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

bool cmp_id(node a,node b){return a.id < b.id;}

int c[MAXN];

int lowbit(int x){return x & (-x);}

void add(int p){for(int i = p;i <= n;i += lowbit(i)){c[i] += 1;}return;}

int query(int p){int res = 0;for(int i = p;i >= 1;i -= lowbit(i))res += c[i];return res;}

int main()

{

	scanf("%d",&n);

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

	{

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

		s[i].id = i;

	}

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

	for(int i = 1;i <= n;++i)s[i].x = i;

	sort(s + 1,s + 1 + n,cmp_id);

	int ans = 0;

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

	{

		add(s[i].x);

		ans = max(ans,i - query(i));

	}

	cout << (ans == 0 ? 1 : ans) << endl;

	return 0;

}