[IOI Camp Judge 26]區間MEX (題目備份)

IOI Camp Judge是暫時性的，因此在此做題目備份
題解在這裡

區間MEX

Time Limit: 5s

Description

定義一個非負整數形成集合的 mex（minimum excludant）為最小不在該集合的非負整數，例如：

• mex({1,2,3})=0
• mex({0,1,2,3,5,8})=4

現在給你一個長度 N 的序列 A，你要支援以下詢問：

• 求一個區間內所有數形成的集合的 mex 值。

Input Format

第一行有一個正整數 T，代表總共有幾筆測試資料。

每筆測試資料第一行包含兩個正整數 N,M，代表序列的長度以及詢問數。
接下來包含 N 個由空白隔開的非負整數 Ai，代表序列的元素。
接下來包含 M 行，每行包含兩個正整數 l,r，
代表一個詢問，請輸出區間 {Al,…,Ar} 的 mex 值。

• 1≤T≤20
• 1≤N,M≤105
• 0≤Ai≤109
• 詢問： 1≤l≤r≤N

Output Format

對於每個詢問，請輸出一行包含一個非負整數，代表該詢問區間的 mex。

Sample Input

1
10 7
1 0 2 3 1 5 4 6 3 7
1 1
1 3
6 10
3 5
4 9
2 3
1 10

Sample Output

0
3
0
0
0
1
8