← 返回题目列表

AtCoder · pakencamp_2023_day1_i

I. 交换和排序

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

配点 : 400 点

問題文

正整数 K 和长度 给出了 N 的正整数序列 给出了 A 。您可以对此序列执行以下操作: 执行次数不得超过 5\times 10^5 次。 交换

  • 整数 i\ (1 \le i \le N-1) 选择… A_i 和 按字典顺序比较 A_{i+1} 后, A_{i+1} 至 该值是 K 。

最终序列按升序排列,即 请找到一个类似于 A_1 \le A_2 \le \ldots \le A_N 的操作序列。此外,可以证明在该约束下存在这样的操作序列。

制約

  • 1 \leq N \leq 1000
  • 1 \le K \le 10^9
  • 1 \le A_i \le 10^9
  • 所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

N K
A_1 A_2 \ldots A_N

出力

操作次数 通过选择 M (0 \le M \le 5\times 10^5) , M+1 行。 1 在线 M 输出… k + 1\ (1 \le k \le M) 在线 k 第一次入选 按以下格式输出为 i 。


入力例 1

4 1
1 3 1 2

出力例 1

2
2
3

i该值应乘以2,3并执行操作两次, 有A=(1,1,2,5)。


入力例 2

8 2
3 1 4 1 5 9 2 6

出力例 2

15
1
2
3
4
5
6
7
2
3
5
6
4
5
3
4