← 返回题目列表

AtCoder · utpc2022_j

J. 划分和排序

中文机器翻译题面 查看原题

配点 : 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 请输出。