#include <cstdio>
#include <fstream>
#include <iostream>

//FILE *fin = fopen("eliminare.in" , "r");
//FILE *fout = fopen("eliminare.out" , "w");
std::ifstream fin("eliminare.in");
std::ofstream fout("eliminare.out");

#define DIM 4*1000000+20

int Arb[DIM],Elm[DIM],n,m,i,j,pos,val,in,sf,x,maxi,A,B,l,r;

int FuncMaxim(int x ,int y)
{
    if( x > y )
        return x;
    else
        return y;
}

void FuncUpdate(int nod, int left, int right)
{
    if( left == right )
    {
        Arb[ nod ] = x;
        Elm[ nod ] = 1;
        return;
    }

    int middle = ( left + right ) / 2;

    if( middle >= pos )
        FuncUpdate( 2 * nod , left , middle );
    else
        FuncUpdate( 2 * nod + 1 , middle + 1 , right );

    Arb[ nod ] = FuncMaxim( Arb[ 2 * nod ] , Arb[ 2 * nod + 1 ] );
    Elm[ nod ] = Elm[ 2 * nod ] + Elm[ 2 * nod + 1 ];
}

void FuncFindElim(int nod, int left, int right, int nr )
{
    int middle = ( left + right ) / 2;

    if( nr == 0 )
    {
        return;
    }

    if( left == right )
    {
        maxi = left;
        return;
    }

    if( Elm[ 2 * nod ] <= nr )
    {
        nr -= Elm[ 2 * nod ];
        maxi = middle;
        FuncFindElim( 2 * nod + 1 , middle + 1 , right , nr );
    }
    else
    {
        FuncFindElim( 2 * nod , left , middle , nr );
    }
}

void FuncSolve(int nod, int left, int right, int start, int finish)
{

    if( left >= start && right <= finish )
    {
        if( Arb[ nod ] > maxi )
        {
            maxi = Arb[ nod ];
            pos = nod;
            l = left;
            r = right;
        }
        return;
    }

    if( left > finish || right < start )
        return;

    int middle = ( left + right ) / 2;

    FuncSolve( 2 * nod , left , middle , start , finish );
    FuncSolve( 2 * nod + 1 , middle + 1 , right , start , finish);

}

void FuncElim(int nod , int left, int right)
{
    if( left == right )
    {
        Arb[ nod ] = -1;
        Elm[ nod ] = 0;
        pos = nod;
    }

    int middle = ( left + right ) / 2;

    if( Arb[ 2 * nod ] == maxi )
    {
        FuncElim( 2 * nod , left , middle );
    }
    else if( Arb[ 2 * nod + 1 ] == maxi )
    {
        FuncElim( 2 * nod + 1 , middle + 1 , right );
    }
}
void FuncUpdateElim(int nod)
{
    Arb[ nod ] = FuncMaxim( Arb[ 2 * nod ] , Arb[ 2 * nod + 1 ] );
    Elm[ nod ] = Elm[ 2 * nod ] + Elm[ 2 * nod + 1 ];

    if( nod == 1 )
        return;

    FuncUpdateElim( nod / 2 );
}

void FuncWrite(int nod, int left, int right)
{
    if( left == right )
    {
        if( Elm[ nod ] == 1 )
        {
            //std::cerr<<Arb[nod]<<' ';
            fout<<Arb[ nod ]<<'\n';  //fprintf( fout , "%d\n" , Arb[ nod ] );
        }
        return;
    }

    int middle = ( left + right ) / 2;

    FuncWrite( 2 * nod , left , middle);
    FuncWrite( 2 * nod + 1 , middle + 1 , right );
}

int main()
{
    fin>>n>>m;  //fscanf( fin,"%d %d",&n,&m );
    for( i = 1 ; i <= n ; ++i )
    {
        fin>>x;//fscanf( fin , "%d" , &x );
        pos = i;
        val = x;
        FuncUpdate( 1 , 1 , n );
    }

    for( i = 1 ; i <= m ; ++i )
    {
        fin>>in>>sf; //fscanf( fin , "%d %d" , &in , &sf );

        maxi = 0;
        if(in != 1)
            FuncFindElim( 1 , 1 , n , in );
        else
            maxi = 1;
        A = maxi;

        maxi = 0;
        FuncFindElim( 1 , 1 , n , sf );
        B = maxi;

        in = A;
        sf = B;
        //std::cerr<<i<<' '<<A<<' '<<B<<'\n';
        maxi = 0;


        FuncSolve( 1 , 1 , n , in , sf );
        FuncElim( pos , l , r );
        FuncUpdateElim( pos / 2 );
        //std::cerr<<"LOLOL ";
        //FuncWrite(1 , 1 , n);
        //std::cerr<<"\n";
    }

    FuncWrite( 1 , 1 , n );

return 0;
}