Background

刘海喜欢$mex$，所以扔给你一个区间$mex$问题

Description

给你一个数组$a$, 进行$q$次询问，每次询问$l,r$,求出$a_l,a_{l+1},.....,a_r$的mex值

$mex\{a,b,c,\dots\}$是的值为，集合中第一个未出现的整数的值，比如$mex\{0,1,2,3,5,6\} = 4$ , $mex\{1,2,2,3,4\} = 0。$

Format

Input

第一行给出两个数$n,q$ $(1\le N \le 2e5,1 \le q \le 2e5)$，接下来一行给出$n$个数$a_i(0\le a_i \le 2e5)$,接下来$q$行，每行有两个数$l,r(1\le l \le n, 1\le r \le n,l\le r)$

Output

输出q行，每行一个数,表示mex的值

Samples

6 2
0 1 2 3 5 6
1 2
1 5

2
4