ZUFEOJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs
Login Register

7961: Rmq Problem

内存限制：128 MB 时间限制：1 S 标准输入输出
题目类型：传统 评测方式：文本比较 上传者：
提交：2 通过：2
提交提交记录统计Web Board

题目描述

请在原题提交：https://www.luogu.com.cn/problem/P4137

题目描述

有一个长度为 n 的数组 {a1,a2,…,an}。
m 次询问，每次询问一个区间内最小没有出现过的自然数。

输入格式

第一行，两个正整数 n,m。
第二行，n 个非负整数 a1,a2,…,an。
接下来 m 行，每行两个正整数l,r，表示一次询问。

输出格式

输出 m 行，每行一个数，依次表示每个询问的答案。

输入输出样例

输入  
5 5
2 1 0 2 1
3 3
2 3
2 4
1 2
3 5
输出  
1
2
3
0
3

说明/提示


对于 100\%100% 的数据：1≤n,m≤2×105，1≤l≤r≤n，0≤ai≤2×105。 




    

  

    
        

        

          
输入样例
          复制
          

          
          

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

          

        

    

        

        

          
输出样例
          复制
          

          
          

            
              
1
2
3
0
3

            
          

        

    

            

      

        

        分类标签