题目描述

题目译自 JOISC 2025 Day1 T1 「展覧会 3 / Exhibition 3」

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$ 幅画作 $(L_j, L_j+1, \ldots, R_j)$。杂志 $j$ 的文章吸引力定义为其拍摄范围内画作美感值的最大值。

JOI 美术馆的馆长 JOI 君希望通过巧妙安排画作顺序，让这些杂志写出更具吸引力的文章，从而吸引更多人关注展览。不过，影响力越高的杂志越能触及更多读者，因此他优先希望影响力高的杂志能获得更高的文章吸引力。更准确地说，设杂志 $j$ $(1 \leq j \leq M)$ 的文章吸引力为 $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'$。

现在，给你展览的画作信息和前来采访的杂志信息，你需要编写一个程序，计算在画作排列顺序使数列 $b = (b_1, b_2, \ldots, b_M)$ 字典序最大时，每家杂志的文章吸引力。

输入格式

第一行包含两个整数 $N,M$。

第二行包含用空格分隔的 $N$ 个整数 $A_1, A_2, \ldots ,A_N$。

接下来的 $M$ 行，每行包含两个整数 $L_i,R_i$。

输出格式

输出 $M$ 行。设杂志 $j$ $(1 \leq j \leq M)$ 的文章吸引力为 $b_j$，第 $j$ 行需输出 $b_j$。数列 $b = (b_1, b_2, \ldots, b_M)$ 必须在字典序上达到最大。

4 4
1 2 1 2
1 1
2 3
4 4
3 4

2
2
1
2

4 8
1 2 3 4
1 2
2 3
4 4
1 1
2 4
3 3
3 3
4 4

4
4
3
2
4
1
1
3

12 10
6 2 2 5 2 5 2 3 3 3 2 2
3 5
10 12
12 12
2 4
8 9
10 11
1 3
7 9
9 10
10 11

6
5
5
6
5
3
6
5
5
3

数据范围与提示

对于所有输入数据，满足：

• $1 \leq N \leq 100000$
• $1 \leq M \leq 100000$
• $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)$
• 所有输入值均为整数

详细子任务附加限制及分值如下表所示。