配点 : 100 点
問題文
(1,2,\ldots,N) 的排列 给出了 P = (P_1,P_2,\ldots,P_N) 。你可以执行以下操作 您可以执行此操作超过 0 回以上 15 次。
- 1\leq l \leq r \leq N 和 r-l+1 由奇数构成的整数组合 (l,r) 被选中,数列 (P_l,P_{l+1},\ldots,P_r) 的中位数由 M 。此时 P_x = M 整数 x 唯一确定。将第P 可以得到第 l 起 件数最多为 x-1 个(如果存在)按升序排列,将第x+1 起 件数最多为 r 个(如果存在)按升序排列。判断
通过操作 P 是否可以按升序排列,并在可能的情况下求出这样的一列操作。
中的中位数是:
长度 小于或等于 2n - 1 数列的中位数是,当数列按升序排列时,从前数到 n 被定义为第几项的值。例如,(5, 4,2) 的中值为 4 、(3,1,5,2,4) 的中值为 3 、(9) 的中值为 9 。制約
- 所有输入均为整数
- 1 \leq N \leq 2\times 10^5
- P 是 您也可以写 (1,2,\ldots,N) 的排列 给出了
部分点
- 1 \leq N \leq 7 的数据集 给出 10 点。 如果您正确回答了所有满足
入力
输入是按以下格式从标准输入给出的。
N P_1 P_2 \ldots P_N
出力
15 通过不超过几次的操作 P 无法按升序排列时 -1 。
如果没有,1 输出在第几行进行操作的次数 k 。这里 k 是 您也可以写 0 以上 15 必须是以下整数。
接下来,k 按行输出操作序列。
i\ (2\leq i \leq k +1) 行中,i-1 在第几次操作中选择 l,r 以空格分隔。
如果有多个解决方案,则任何输出都将被视为正确。
入力例 1
5 2 1 3 5 4
出力例 1
1 1 5
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
4 1 2 3 4
出力例 2
2 1 3 2 4
15 如果在几次以内操作,则无需最小化操作次数。
入力例 3
2 2 1
出力例 3
-1
15 在几次以内操作 P 无法按升序排列时, -1 请输出。