#include <bits/stdc++.h>
#define NMAX 1000005
#define INF 1e9
using namespace std;

ifstream fin("eliminare.in");
ofstream fout("eliminare.out");
struct sol{
    int s,p,l;
};
sol V[4 * NMAX];
int S[NMAX];
bitset < NMAX > B;

inline void buildtree(int nod,int L,int R){
    if(L == R){
        V[nod].s = S[L];
        V[nod].p = L;
        return;
    }
    int mid = (L + R) / 2;

    buildtree(2 * nod,L,mid);
    buildtree(2 * nod + 1,mid + 1,R);
        if(V[2 * nod].s >= V[2 * nod + 1].s)
            V[nod].s = V[2 * nod].s,V[nod].p = V[2 * nod].p;
        else
            V[nod].s = V[2 * nod + 1].s,V[nod].p = V[2 * nod + 1].p;

}

inline void Search(int nod,int L,int R,int m,int M,int &p,int &mx){
    if(V[nod].l){
        V[nod].s += V[nod].l;
        if(L != R){
            V[2 * nod].l += V[nod].l;
            V[2 * nod + 1].l += V[nod].l;
        }
        V[nod].l = 0;
    }
    if(L > R)
        return;
    if(L >= m && R <= M){
        if(mx < V[nod].s){
            mx = V[nod].s;
            p = nod;
        }
        return;
    }
    int mid = (L + R)/2;
    if(mid >= m)
        Search(2 * nod,L,mid,m,M,p,mx);
    if(mid < M)
        Search(2 * nod + 1,mid + 1,R,m,M,p,mx);

}
inline void update(int nod,int L,int R,int p){
    if(V[nod].l){
        V[nod].s += V[nod].l;
        if(L != R){
            V[2 * nod].l += V[nod].l;
            V[2 * nod + 1].l += V[nod].l;
        }
        V[nod].l = 0;
    }
    if(L == R){
        V[nod].s = -INF;
        return;
    }
    int mid = (L + R)/2;

    if(mid >= p)
        update(2 * nod,L,mid,p);
    else
        update(2 * nod + 1,mid + 1,R,p);

    if(V[2 * nod].s >= V[2 * nod + 1].s)
        V[nod].s = V[2 * nod].s,V[nod].p = V[2 * nod].p;
    else
        V[nod].s = V[2 * nod + 1].s,V[nod].p = V[2 * nod + 1].p;

}

inline void solve(int nod,int L,int R){
    if(V[nod].l){
        V[nod].s += V[nod].l;
        if(L != R){
            V[2 * nod].l += V[nod].l;
            V[2 * nod + 1].l += V[nod].l;
        }
        V[nod].l = 0;
    }
    if(L == R){
        if(V[nod].s > -INF)
            fout << V[nod].s << " ";
        return;
    }
    int mid = (L + R) / 2;

    buildtree(2 * nod,L,mid);
    buildtree(2 * nod + 1,mid + 1,R);


}


inline void lazyupdate(int nod,int L,int R,int m,int M,int c){
    if(L > R)
        return;
    if(V[nod].l){
        V[nod].s += V[nod].l;
        if(L != R){
            V[2 * nod].l += V[nod].l;
            V[2 * nod + 1].l += V[nod].l;
        }
        V[nod].l = 0;
    }
    if(R >= m && L <= M){
        V[nod].s += c;
        if(L != R){
            V[2 * nod].l += c;
            V[2 * nod + 1].l += c;
        }
        return;
    }
    int mid = (R + L) / 2;
    if(mid >= m)
        lazyupdate(2 * nod,L,mid,m,M,c);
    if(mid < M)
        lazyupdate(2 * nod + 1,mid + 1,R,m,M,c);

    if(V[2 * nod].s >= V[2 * nod + 1].s)
        V[nod].s = V[2 * nod].s,V[nod].p = V[2 * nod].p;
    else
        V[nod].s = V[2 * nod + 1].s,V[nod].p = V[2 * nod + 1].p;
}

int main()
{
    ios :: sync_with_stdio(false);
    fin.tie(NULL);

    int n,m,p,x,y,mx;
    fin >> n >> m;

    for(int i = 1; i <= n; i++)
        fin >> S[i];
    buildtree(1,1,n);

    for(int i = 1; i <= m; i++){
        fin >> x >> y;
        mx = -INF;
        Search(1,1,n,x,y,p,mx);
        p = V[p].p;
        fout << p << " ";
        update(1,1,n,p);
        if(p != 1)
            lazyupdate(1,1,n,1,p - 1, -1);

    }
    solve(1,1,n);
    return 0;
}