#include<bits/stdc++.h>
 #define mid ((l + r) >> 1)
 #define min(x,y) x < y ? x : y
 #define pushup(x) Tree[x].minN = min(Tree[Tree[x].l].minN , Tree[Tree[x].r].minN)
 //This code is written by Itst
 using namespace std;

 inline int read(){
     ;
     ;
     char c = getchar();
     while(c != EOF && !isdigit(c)){
         if(c == '-')
             f = ;
         c = getchar();
     }
     while(c != EOF && isdigit(c)){
         a = (a << ) + (a << ) + (c ^ ');
         c = getchar();
     }
     return f ? -a : a;
 }

 ;
 struct query{
     int l , r , ind;
 }que[MAXN];
 struct node{
     int l , r , minN;
 }Tree[MAXN * ];
 int ans[MAXN] , root[MAXN] , N , M , cntNode;

 void insert(int& x , int p , int l , int r , int tar , int num){
     x = ++cntNode;
     Tree[x] = Tree[p];
     if(l == r)
         Tree[x].minN = num;
     else{
         if(mid >= tar)
             insert(Tree[x].l , Tree[p].l , l , mid , tar , num);
         else
             insert(Tree[x].r , Tree[p].r , mid +  , r , tar , num);
         pushup(x);
     }
 }

 int query(int x , int l , int r , int minN){
     if(l == r)
         return l;
     if(Tree[Tree[x].l].minN < minN)
         return query(Tree[x].l , l , mid , minN);
      , r , minN);
 }

 int main(){
 #ifndef ONLINE_JUDGE
     freopen("4137.in" , "r" , stdin);
     //freopen("4137.out" , "w" , stdout);
 #endif
     N = read();
     M = read();
      ; i <= N ; ++i){
         int a = read();
         if(a < N)
             insert(root[i] , root[i - ] ,  , N , a , i);
         else
             root[i] = root[i - ];
     }
      ; i <= M ; ++i){
         int a = read() , b = read();
         printf( , N , a));
     }
     ;
 }