题目背景

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

题目描述

樱有一个长度为 $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$，输出一个整数表示答案。

7 3
0 1 4 1 5 1 4
1 3
1 6
5 7

-1
2
3
3
6
7
8
9

提示

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

::cute-table{tuack}

特殊性质 A：$A_i=n-1$。

特殊性质 B：$\sum(r_i-l_i+1)\le 100$。