P14201 樱

只属于我们两人的樱花不畏寒冬，大肆绽放。

樱有一个长度为 $n$ 的序列 $A$。她现在有 $m$ 个问题，第 $i$ 个问题是：$\operatorname{mex}(A_{l_i},A_{l_{i+1}},\dots,A_{r_i})$ 的值为多少。 抱月想要给樱改改题。具体地，她将构造一个长度为 $k$ 的序列 $B$。那么樱的第 $i$ 个问题将变成：求 $\operatorname{mex}(A_{l_i},A_{l_{i+1}},\dots,A_{r_i},B_1,B_2,\dots,B_k)$。 如果对于所有 $m$ 个问题，在樱通过一切方式求出来后都是相同的，那么樱会有成就感。 抱月想知道，当 $k=0,1,\dots,n$ 时，是否能构造出来一个长度为 $k$ 的序列 $B$，使得樱开心。如果可以，那么这 $m$ 个问题的答案的最大值是多少。如果不可以，请输出 $-1$。 **【形式化题面】**： 给定一个长度为 $n$ 的序列 $A$ 与 $m$ 组 $l_i,r_i$。 要构造一个长度为 $k$ 的序列 $B$，记 $f_i=\operatorname{mex}(A_{l_i},A_{l_i+1},\dots,A_{r_i},B_1,B_2,\dots,B_k)$。那么有：$f_i(1 \le i \le m)$ 相等。 对于 $k=0,1,\dots ,n$，求在所有满足条件的 $B$ 中，$f_i$ 值最大是多少。若不存在任何一个 $B$，则最大值为 $-1$。 **注**： $\operatorname{mex}(A_{1},A_{2},A_{3},\dots,A_m)$ 为可重集 $\{A_1,A_2,A_3,\dots,A_m\}$ 中最小的不存在的**自然数**。

第一行两个整数 $n,m$。 第二行 $n$ 个整数 $A_i$。 接下来 $m$ 行，每行两个整数 $l_i,r_i$。

对于每个 $k$，输出一个整数表示答案。

对所有数据，满足 $1 \le n,m \le 10^6,0 \le A_i