题目描述
给定 1,…,n 的一个排列 a。一次操作选择区间 [l,r]。将这一段中相对位置为 2,4,6,… 的元素按原顺序放在前面,再将相对位置为 1,3,5,… 的元素按原顺序放在后面。区间外的元素保持不变。
例如,对 [2,4,1,5,3,6,7,8] 执行 [2,6],子数组 [4,1,5,3,6] 变为 [1,3,4,5,6],得到 [2,1,3,4,5,6,7,8]。
请输出一组不超过 6000 次的操作,将排列变成升序。
输入格式
第一行一个整数 n。第二行 n 个整数 a1,…,an。
输出格式
第一行一个整数 k,表示操作次数,要求 0≤k≤6000。接下来 k 行,每行两个整数 l,r,表示按顺序执行一次区间操作,要求 1≤l≤r≤n。
操作次数无需最小,保证至少存在一组满足上限的方案。
样例 1
5
3 1 4 2 5
1
1 5
样例 2
8
2 4 1 5 3 6 7 8
2
2 6
1 2
数据范围
1≤n≤3000,a 是 1,…,n 的排列。设 k0 为最少操作次数,有 0≤k0≤6000。
| 原子任务 |
分值 |
n 上界 |
附加限制 |
| 1 |
20 |
100 |
k0=1 |
| 2 |
30 |
|
| 3 |
1000 |
| 4 |
20 |
3000 |
原 PDF 题面