//Knapsack DP is harder than FFT.
#include<bits/stdc++.h>
using namespace std;
//types
typedef long long ll;
typedef pair<int,int> pii;
//input
bool SR(int &_x){return scanf("%d",&_x)==1;}bool SR(ll &_x){return scanf("%lld",&_x)==1;}
bool SR(double &_x){return scanf("%lf",&_x)==1;}bool SR(char *_x){return scanf("%s",_x)==1;}
bool RI(){return true;}
template<typename I,typename... T>bool RI(I &_x,T&... _tail){return SR(_x) && RI(_tail...);}
//output
void SP(const int _x){printf("%d",_x);}void SP(const ll _x){printf("%lld",_x);}
void SP(const double _x){printf("%.12lf",_x);}void SP(const char *_x){printf("%s",_x);}
void PL(){puts("");}
template<typename I,typename... T>void PL(const I _x,const T... _tail)
{SP(_x);if(sizeof...(_tail))putchar(' ');PL(_tail...);}
//macro
#define SZ(x) ((int)(x).size())
#define AI(x) (x).begin(),(x).end()
#define FOR(i,n) for(int i=0;i<(n);++i)
#define FOO(i,a,b) for(int i=(a);i<=int(b);++i)
#define OOF(i,a,b) for(int i=(a);i>=int(b);--i)
#define pb emplace_back
#define ff first
#define ss second
template<typename I> bool chmax(I &a, I b){ return a < b ? (a = b, true) : false;}
template<typename I> bool chmin(I &a, I b){ return b < a ? (a = b, true) : false;}
//debug
#ifdef OWO
template<typename A,typename B>
ostream& operator<<(ostream& _s, const pair<A,B> &_p){return _s<<'('<<_p.ff<<','<<_p.ss<<')';}
template<typename It>ostream& _OUTC(ostream& _s,It _b,It _e){
    _s<<'{';
    for(auto _it=_b;_it!=_e;++_it) _s<<(_it==_b?"":" ")<<*_it;
    _s<<'}';
    return _s;
}
template<typename A,typename B>
ostream& operator <<(ostream&_s, const map<A,B> &_c){return _OUTC(_s,AI(_c));}
template<typename T>
ostream& operator <<(ostream&_s, const set<T> &_c){return _OUTC(_s,AI(_c));}
template<typename T>
ostream& operator <<(ostream&_s, const vector<T> &_c){return _OUTC(_s,AI(_c));}
template<typename I>
void _DOING(const char *_s,I&& _x){cerr<<_s<<'='<<_x<<endl;}
template<typename I,typename... T>
void _DOING(const char *_s,I&& _x,T&&... _tail){
    int _c=0;
    static const char _bra[]="([{";
    static const char _ket[]=")]}";
    while(*_s!=',' || _c!=0){
        if(strchr(_bra,*_s)) _c++;
        if(strchr(_ket,*_s)) _c--;
        cerr<<*_s++;
    }
    cerr<<'='<<_x<<", ";
    _DOING(_s+1,_tail...);
}
#define debug(...) do{\
    fprintf(stderr,"%s:%d - ",__PRETTY_FUNCTION__,__LINE__);\
    _DOING(#__VA_ARGS__,__VA_ARGS__);\
}while(0)
#else
#define debug(...)
#endif
const int N = 2e5 + 225;
struct segtree{
    int val[N<<2];
    void init(){
        memset(val, -1, sizeof(val));
    }
    void modify(int p, int v, int x, int l, int r){
        if(l == r){
            val[x] = v;
            return;
        }
        int m = (l + r) / 2;
        if(p <= m) modify(p, v, x * 2, l, m);
        else modify(p, v, x * 2 + 1, m+1, r);
        val[x] = min(val[x*2], val[x*2+1]);
    }
    void modify(int p, int v){
        modify(p, v, 1, 0, N);
    }
    int query(int v, int x, int l, int r){
        if(l == r) return l;
        int m = (l + r) / 2;
        if(val[x * 2] >= v) return query(v, x * 2 + 1, m+1, r);
        return query(v, x * 2, l, m);
    }
    int query(int v){
        return query(v, 1, 0, N);
    }
} sgt;

int n, m, a[N], id[N], ans[N];
pii q[N];

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> m;
    FOO(i,1,n) cin >> a[i];
    FOR(i,m) cin >> q[i].ff >> q[i].ss, id[i] = i;
    sort(id, id + m, [](int a, int b){ return q[a].ss < q[b].ss;});
    sgt.init();
    int cur = 0;
    FOR(i,m){
        while(cur < q[id[i]].ss) sgt.modify(a[++cur], cur);
        ans[id[i]] = sgt.query(q[id[i]].ff);
    }
    FOR(i,m) cout << ans[i] << '\n';
    return 0;
}