JOI 美术馆近期将举办一场画作展览。美术馆馆藏有 $N$ 幅编号为 $1$ 到 $N$ 的画作，其中第 $i$ 幅画（$1 \leq i \leq N$）的美丽度为 $A_i$。在展览中，这些画作将从左到右按一条直线顺序摆放，具体的排列顺序尚未确定。

届时，将有 $M$ 家杂志前来采访。这些杂志按照影响力从高到低依次编号为 $1$ 到 $M$，每家杂志计划从展览中连续的一段画作中拍摄照片并发表报道。具体而言，第 $j$ 家杂志（$1 \leq j \leq M$）将对从左起第 $L_j$ 到 $R_j$ 幅画作进行拍照报道。此时，第 $j$ 家杂志的报道“魅力度”定义为他们所选区间内画作美丽度的最大值。

JOI 美术馆的馆长 JOI 君希望通过巧妙安排画作的顺序，使得这些杂志能报道出更具魅力的文章，从而吸引更多观众关注展览。由于影响力越高的杂志影响的人群越多，因此应优先保证影响力高的杂志所报道的魅力度更高。更准确地说，设每家杂志的报道魅力度依次为 $b_j$，JOI 君希望通过排列画作，使得数列 $b=(b_1,b_2,\ldots,b_M)$ 的字典序最大。对于两个不同的数列 $b=(b_1,b_2,\ldots,b_M)$ 和 $b'=(b'_1,b'_2,\ldots,b'_M)$，若存在最小的 $k$（$1 \leq k \leq M$），使得 $b_k \neq b'_k$ 且 $b_k > b'_k$，则称 $b$ 的字典序比 $b'$ 大。

现给出本次展览的所有画作信息及前来采访的杂志的信息，请你编程输出在字典序最大的情况下，每家杂志的报道魅力度。

---

输入为标准输入，格式如下：

$N$  $M$
$A_1\  A_2\ \ldots\  A_N$
$L_1\  R_1$
$L_2\  R_2$
$\vdots$
$L_M\  R_M$

请按顺序输出 $M$ 行，第 $j$ 行输出第 $j$ 家杂志的报道魅力度 $b_j$。数列 $b=(b_1,b_2,\ldots,b_M)$ 必须为字典序最大的。

小题目

1. （$19$ 分）$N \leq 400，M \leq 400$。
2. （$9$ 分）$N \leq 400$。
3. （$19$ 分）$A_i\leq 5$（$1\leq i \leq N$）。
4. （$12$ 分）$A_i=i$（$1\leq i\leq N$）。
5. （$17$ 分）对于任意 $k$（$1\leq k\leq N$），满足 $A_i=k$ 的 $i$（$1\leq i\leq N$）至多 $5$ 个。
6. （$24$ 分）无额外限制。

---

样例解释 1

若按 $2,\,3,\,4,\,1$ 的顺序排列，得到每家杂志的报道魅力度如下：

• 杂志 $1$：仅包含第 $2$ 幅画，其美丽度为 $2$，魅力度为 $2$。
• 杂志 $2$：包含第 $3,4$ 幅画，其美丽度分别为 $1, 2$，最大值为 $2$，魅力度为 $2$。
• 杂志 $3$：仅包含第 $1$ 幅画，其美丽度为 $1$，魅力度为 $1$。
• 杂志 $4$：包含第 $4,1$ 幅画，其美丽度分别为 $2$ 和 $1$，最大值为 $2$，魅力度为 $2$。

此时数列 $b=(2,2,1,2)$。不存在比这更大字典序的画作顺序，因此答案为按顺序输出 $2,2,1,2$。

该样例输入满足小题目 $1,2,3,5,6$ 的约束。

---

样例解释 2

本样例输入满足所有小题目的约束。

---

样例解释 3

本样例输入满足小题目 $1,2,6$ 的约束。

约束条件

• $1 \leq N \leq 100\,000$。
• $1 \leq M \leq 100\,000$。
• $1 \leq A_i \leq N$（$1 \leq i \leq N$）。
• $1 \leq L_j \leq R_j \leq N$（$1 \leq j \leq M$）。
• 所有输入数值均为整数。

由 ChatGPT 5 翻译