题目分析

给定一个长度为 $n$ 的初始全零数组，进行了 $m$ 次区间赋值操作，第 $i$ 次操作将区间 $[l_i, r_i]$ 内的所有元素赋值为 $i$。我们仅给出最终数组 $a$，要求还原每一次操作的区间 $[l_i, r_i]$。

• 数组长度和操作次数均可达 $10^5$，需 $O(n + m)$ 或 $O((n + m) \log n)$ 复杂度。
• 操作会互相覆盖，后面的操作会覆盖前面的值，最终数组中某些值可能完全被覆盖而不出现。
• 数据保证存在解。

解题思路

1. 记录出现区间：对每个操作编号 $i$，在最终数组中记录它第一次出现的位置为 $\mathrm{L}[i]$，最后一次出现的位置为 $\mathrm{R}[i]$。如果某 $i$ 在最终数组中出现，则它的真实区间必包含这段连续区域，且可能被后续操作打断。
2. 填补未出现编号：对于没有在最终数组中出现的编号 $i$，说明操作 $i$ 的区间被后续所有操作完全覆盖。我们可以将其区间选在任意一个后续出现编号的区间内部。具体做法是对 $i$ 从 $m$ 递减到 $1$：

题目内容

小红有一个长度为$n$的数组{$a_1,a_2,...,a_n$},数组初值全部为$0$，小红会进行$m$次操作，第$i$次操作为将区间$[l_i,r_i]$内的数全部修改为$i$。

现在小红拿到了$m$次操作之后的数组$a$，小红想知道每一次操作的区间$[l_i,r_i]$。

输入描述

第一行输入两个整数$n,m(1≤n,m≤10^5)$，表示数组长度和操作次数。

第二行输入$n$个整数$a_1,a_2,...,a_n(0≤a_i≤m)$,表示$m$次操作之后的数组。

输出描述

输出$m$ 行，每行两个整数$l_i,r_i$，表示第$i$次操作的区间。如果有多种答案，输出任意一种。数据保证答案存在。

样例1

输入

5 4
1 2 4 2 3

输出

1 5
2 4
5 5
3 3

说明

第一次操作将区间$[1,5]$内的数全部修改为$1$，得到数组$[1,1, 1, 1, 1]$。

第二次操作将区间$[2,4]$内的数全部修改为$2$，得到数组$[1,2,2, 2,1]$。

第三次操作将区间$[5,5]$内的数全部修改为$3$，得到数组$[1,2,2,2,3]$。

第四次操作将区间$[3,3]$内的数全部修改为$4$，得到数组$[1,2,4,2,3]$。