配点 : 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
也有可能在不进行操作的情况下,就已经成为恒等的阿弥陀籤了。