AT_utpc2022_j.Divide and Sort

给定 $(1,2,\ldots,N)$ 的一个排列 $P=(P_1,P_2,\ldots,P_N)$。你可以进行如下操作，操作次数不少于 $0$ 次且不多于 $15$ 次。

• 选择一组整数 $(l,r)$，满足 $1\leq l\leq r\leq N$ 且 $r-l+1$ 为奇数，将数列 $(P_l,P_{l+1},\ldots,P_r)$ 的中位数设为 $M$。这时，存在唯一的整数 $x$ 满足 $P_x=M$。将 $P$ 的第 $l$ 项到第 $x-1$ 项（如果存在）按升序排序，将 $x+1$ 项到第 $r$ 项（如果存在）按升序排序。

请判断是否可以通过不超过 $15$ 次操作将 $P$ 排成升序排列。如果可以，请输出一种操作序列。

中位数的定义为：长度为 $2n-1$ 的数列的中位数，是将该数列升序排列后，从前往后第 $n$ 个元素的值。例如，$(5,4,2)$ 的中位数是 $4$，$(3,1,5,2,4)$ 的中位数是 $3$，$(9)$ 的中位数是 $9$。

输入从标准输入以如下格式给出。

$N\ P_1\ P_2\ \ldots\ P_N$

如果无法在 $15$ 次以内（含 $15$ 次）将 $P$ 排成升序排列，则输出 $-1$。

否则，第一行输出操作次数 $k$，其中 $k$ 是 $0$ 到 $15$（含）之间的整数。

接下来 $k$ 行，每行两个以空格分隔的整数 $l$ 和 $r$，表示每次操作选择的区间。

如果有多种答案，可以输出其中任意一种。

部分分

• 若能正确解决所有 $1\leq N\leq 7$ 的数据，将获得 $10$ 分。

样例解释 1

对 $l=1,r=5$ 进行一次操作。

数列 $(2,1,3,5,4)$ 的中位数为 $3$，且 $P_x=3$ 的 $x=3$。将 $P$ 的 $l=1$ 到 $x-1=2$ 排序，以及 $x+1=4$ 到 $r=5$ 排序。

该操作后，$P$ 变为 $(1,2,3,4,5)$，确实变为升序排列。

样例解释 2

只要操作次数不超过 $15$，不要求操作次数最少。

样例解释 3

若无法在 $15$ 次以内操作将 $P$ 升序化，请输出 $-1$。

数据范围

• 输入均为整数
• $1 \leq N \leq 2\times 10^5$
• $P$ 是 $(1,2,\ldots,N)$ 的一个排列

由 ChatGPT 5 翻译