题目描述

有 $n$ 枚硬币，硬币的价值均为正整数，编号为 $1,2,\ldots,n$。

你需要处理 $q$ 次询问。每次询问给出区间 $[a,b]$，表示你只能使用编号为 $a,a+1,\ldots,b$ 的硬币。请问在这些硬币中任选若干枚时，最小不能凑出的正整数和是多少。

输入格式

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

第二行包含 $n$ 个整数 $x_1,x_2,\ldots,x_n$，表示每枚硬币的价值。

接下来 $q$ 行，每行包含两个整数 $a,b$，表示一次询问中可使用的硬币编号范围为 $a\ldots b$。

输出格式

对每个询问输出一行一个整数，表示答案。

数据范围

• $1 \le n,q \le 2\cdot 10^5$
• $1 \le x_i \le 10^9$
• $1 \le a \le b \le n$

样例

样例输入

5 3
2 9 1 2 7
2 4
4 4
1 5

样例输出

4
1
6

样例说明

第一次可使用硬币 $[9,1,2]$，第二次可使用 $[2]$，第三次可使用 $[2,9,1,2,7]$。