题目大意：

长度为$n$的序列a，可以将任一区间内的最大最小值位置调换，问从初状态到末状态的一种可行方案数。

$1<=n<=4096$

分析：

考虑归并排序，
对于两个递增的序列[l,mid],[mid+1,r]
从mid向两边拓展，找到最大的x满足
满足$a[mid-x]>a[mid+1+x]$
则显然将这段区间$[mid-x,mid]$,$[mid+1,mid+1+x]$分别翻转以后$[mid-x,mid+1+x]$是一段递减的序列
此时我们再将整个序列翻转一遍就可以使得这一段单调递增
然后我们再去做$(l,mid,x)$和$(mid+1,r,mid+1+x)$即可

代码：

#include <iostream>
#include <cstdio>
#include <cmath>
#include <queue>
#include <cstring>
#include <algorithm>#define rep(i, st, ed) for (int i = st; i <= ed; i++)
#define rwp(i, ed, st) for (int i = ed; i >= st; i--)#define N 5005using namespace std;struct Node {int l, r;Node(){}Node(int a, int b) {l = a, r = b;}
}ans[350000];
int a[N], n, cnt, tot;void merge(int l, int r, int mid) {if (l > mid || mid >= r || l == r) return;int i = mid, j = mid + 1;while(i > l && j < r && a[i - 1] > a[j + 1]) --i, ++j;if (a[i] > a[j]) {for (int p = i, q = mid; p < q; ++p, --q)swap(a[p], a[q]), ans[++tot] = Node(p, q);for (int p = mid + 1, q = j; p < q; ++p, --q)swap(a[p], a[q]), ans[++tot] = Node(p, q);for (int p = i, q = j; p < q; ++p, --q)swap(a[p], a[q]), ans[++tot] = Node(p, q);merge(l, mid, i - 1), merge(mid + 1, r, j);}return;
}void solve(int l, int r) {   if(l == r) return;int mid = (l + r) >> 1;solve(l, mid); solve(mid + 1, r);merge(l, r, mid);return;
}int main() {freopen("swap.in", "r", stdin),freopen("swap.out", "w", stdout);scanf("%d", &n);  rep(i, 1, n) scanf("%d", &a[i]);solve(1, n); cnt = tot; rep(i, 1, n) scanf("%d", &a[i]);solve(1, n);printf("%d\n", tot);rep(i, 1, cnt) printf("%d %d\n", ans[i].l, ans[i].r);rwp(i, tot, cnt + 1) printf("%d %d\n", ans[i].l, ans[i].r);return 0;
}