#P10370. [2021年联测]排序

[2021年联测]排序

题目描述

给定 1,…,n1,\ldots,n 的一个排列 aa。一次操作选择区间 [l,r][l,r]。将这一段中相对位置为 2,4,6,…2,4,6,\ldots 的元素按原顺序放在前面,再将相对位置为 1,3,5,…1,3,5,\ldots 的元素按原顺序放在后面。区间外的元素保持不变。

例如,对 [2,4,1,5,3,6,7,8][2,4,1,5,3,6,7,8] 执行 [2,6][2,6],子数组 [4,1,5,3,6][4,1,5,3,6] 变为 [1,3,4,5,6][1,3,4,5,6],得到 [2,1,3,4,5,6,7,8][2,1,3,4,5,6,7,8]。

请输出一组不超过 60006000 次的操作,将排列变成升序。

输入格式

第一行一个整数 nn。第二行 nn 个整数 a1,…,ana_1,\ldots,a_n。

输出格式

第一行一个整数 kk,表示操作次数,要求 0≤k≤60000\le k\le6000。接下来 kk 行,每行两个整数 l,rl,r,表示按顺序执行一次区间操作,要求 1≤l≤r≤n1\le l\le r\le 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≤30001\le n\le3000,aa 是 1,…,n1,\ldots,n 的排列。设 k0k_0 为最少操作次数,有 0≤k0≤60000\le k_0\le6000。

原子任务 分值 nn 上界 附加限制
1 20 100 k0=1k_0=1
2 30
3 1000
4 20 3000

原 PDF 题面