You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

时空限制

3S/512M

题目描述

给定一个长度为 $n$ 的整数数列 $A$，其中 $A$ 中的元素两两不同。

现有 $q$ 次询问，每次询问给定一个区间 $[l, r]$，请你计算以下两个值的乘积：

1. 区间 $[l, r-1]$ 的最小值，即 $\min(A_l, A_{l+1}, \dots, A_{r-1})$。
2. 区间 $[l, r]$ 的最小未出现的自然数（MEX），即 $\text{MEX}(A_l, A_{l+1}, \dots, A_r)$。

$\text{MEX}(S)$ 定义为不属于集合 $S$ 的最小非负整数。

例如：

• 对于集合 $\{1, 2, 3\}$，因为 $0$ 不在集合中，所以 $\text{MEX} = 0$。
• 对于集合 $\{0, 2, 3\}$，因为 $0$ 在但 $1$ 不在，所以 $\text{MEX} = 1$。
• 对于集合 $\{0, 1, 2\}$，因为 $0, 1, 2$ 都在，所以 $\text{MEX} = 3$。
• 对于集合 $\{ \}$ (空集)，$\text{MEX} = 0$。

格式

输入格式

第一行包含两个整数 $n, q$，分别表示数列长度和询问数量。

第二行包含 $n$ 个整数 $A_i$，表示数列的元素。

接下来 $q$ 行，每行包含两个整数 $l, r$，表示一次询问的区间。

输出格式

输出 $q$ 行，每行一个整数，表示第 $i$ 次询问计算出的乘积。

样例

样例输入 #1

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

样例输出 #1

2
0
2
0

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

对于 $100\%$ 的数据，满足 $1 \leq n, q \leq 10^6$，数列 $A$ 中元素两两不同，$0 \le A_i < n$，$1\leq l < r \leq n$。