← 返回题目列表

AtCoder · tupc2022_j

J. 阿米达

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

配点 : 400 点

問題文

N 有由竖线组成的阿弥陀籤。
每根竖线的长度是 2M+1 [\mathrm{cm}] ,横线必须满足以下条件。

  • 横线的端点只能位于从上数 1,2,\dots,2M [\mathrm{cm}] 的高度,且横线两端的高度必须相等
  • 所有横线只能连接相邻的 2 根竖线
  • 同一高度的横线最多 1 本

一开始,在这个阿弥陀籤上 M 画上了横线。 j\ (j=1,2,\dots,M) 第一本横线从上面开始 2j [\mathrm{cm}] 画在了…的位置,从左边起第 a_j 条竖线和第 a_j+1 条竖线之间连接。

在这个阿弥陀籤上,可以执行以下操作任意次数( 0 次也可以)。

  • 仍未画横线的高度 h 以及、1 以上 N-1 的整数 给出了 b 选择。
    从上面 h [\mathrm{cm}] 的位置,从左开始 b 条竖线和第 b+1 第几根竖线相连的横线进行追加。

全部 i=1,2,\dots,N 针对,若从左数第 i 根竖线开始沿抽签路径,结果是从左数第 i 根的阿弥陀签称为“恒等阿弥陀签”时,请求将给定的阿弥陀签变为恒等阿弥陀签所需的最小操作次数。
此外,实现最小操作次数的操作方法 1 请注明之一。
在该约束下,始终可以证明存在将其变为恒等阿弥陀签的操作方法。

制約

  • 2 \leq N \leq 2\times10^5
  • 1\leq M\leq 2\times10^5
  • 1 \leq a_j < N\ (j=1,2,\dots,M)
  • 所有输入均为整数

入力

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

N M
a_1 a_2 \dots a_M

出力

必要操作次数的最小值 ans ,1+ans 行。
1 在线 ans 输出。 接着 j+1\ (j=1,2,\dots,ans) 在线 j 在第几次操作中从上数第 h_j [\mathrm{cm}] 的位置,从左开始 b_j 条竖线和第 b_j+1 根竖线相连的横线进行追加,h_j,b_j ,用空格分隔。 当


入力例 1

3 2
1 2

出力例 1

2
1 1
3 2

此外,

2
1 2
3 1

也是正确答案。


入力例 2

5 4
2 3 4 1

出力例 2

4
1 2
3 3
5 4
7 1

入力例 3

100000 4
1 2 2 1

出力例 3

0

也有可能在不进行操作的情况下,就已经成为恒等的阿弥陀籤了。