#include <cstdio>
#include <queue>

using namespace std;

#define l 100003
#define IN "arbore.in"
#define OUT "arbore.out"

struct element
{
    int st , dr , val;
}v[l];

int n , m;
queue<int>Q;

int maxi(int a , int b)
{
    if ( a > b )
        return a;
    else return b;
}

int mini(int a , int b)
{
    if ( a < b )
        return a;
    return b;
}

bool Total_Overlap(int a , int b , int x , int y)
{
    if (( a <= x && b >= y ) or ( x <= a or b <= y ))
        return 1;
    return 0;
}

bool Partial_Overlap(int a , int b , int x , int y)
{
    if (( a >= x && a <= y ) or ( b >= x && b <= y ) or ( x >= a && x <= b ) or ( y >= a && y <= b))
        return 1;
    return 0;
}

bool No_Overlap(int a , int b , int x , int y)
{
    if ( Partial_Overlap(a,b,x,y) == 0 && Total_Overlap(a,b,x,y) == 0 )
        return 1;
    return 0;
}

void Build()
{
    int j , i , x;
    j = n;

    for ( i = 1 ; i <= n ; i ++ ){
            scanf ( "%d" , &x );
        if ( i != n )
    {
        v[++j].val = x , v[j].st = v[j].dr = i;
    }
       else
        v[n].val = x , v[n].st = v[n].dr = i;

    }


    for ( i = n - 1 ; i >= 1 ; i -- ){
        v[i].val = maxi(v[i*2].val,v[i*2+1].val) , v[i].st = mini(v[i*2].st,v[i*2+1].st) , v[i].dr = maxi(v[i*2].dr , v[i*2+1].dr);
    }


}

int main()
{
    int x , y , i , j;

    freopen ( IN , "r" , stdin );
    freopen ( OUT , "w" , stdout );

    scanf ( "%d%d" , &n , &m );
    Build();

    for ( i = 1 ; i <= m ; i ++ )
    {
        scanf ( "%d%d" , &x , &y );
        Q.push(1);

        while (!Q.empty())
        {
           j = Q.front();

           if ( Total_Overlap(x,y,v[j].st,v[j].dr) ){
              printf ( "%d " , v[j].val );
              while(!Q.empty())Q.pop();
           }
           else if ( Partial_Overlap(x,y,v[j].st,v[j].dr) )
              Q.push(j*2) , Q.push(j*2+1);

           else if (No_Overlap(x,y,v[j].st,v[j].dr))
            while(Q.empty())Q.pop();

            Q.pop();
        }


    }

}