#5044. 「JOISC 2025 Day1」展览会 3

题目译自 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)$ 必须在字典序上达到最大。

样例 1

输入

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

输出

2
2
1
2

样例 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

样例 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$)
• 所有输入值均为整数

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

子任务	分值	附加限制
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	无附加限制