Rt……求调

//猫树写法
#include<cstdio>
#include<algorithm>
int read(){
    int x=0,f=1;
    char ac=getchar();
    while(ac<'0'||ac>'9'){
        if(ac=='-') f=-1;
        ac=getchar();
    }
    while(ac>='0'&&ac<='9'){
        x=(x<<3)+(x<<1)+(ac-'0');
        ac=getchar();
    }
    return x*f;
}
int cat[19][200005],a[200005],size,logg[800005],q;
void solve(int u,int l,int r){
    int mid=l+r>>1;
    cat[u][mid]=a[mid];
    cat[u][mid+1]=a[mid+1];
    for(int i=mid-1;i>=l;i--) cat[u][i]=std::max(cat[u][i+1],a[i]);
    for(int i=mid+2;i<=r;i++) cat[u][i]=std::max(cat[u][i-1],a[i]);
}
void build(int size){
    int n=1;
    while(n<size) n<<=1;
    if(n==size) n<<=1;
    for(int i=1;i<=n*2;i++) logg[i]=logg[i>>1]+1;
    int pow=0;
    for(int i=1;i<=n;i<<=1){
        for(int j=1;j<=n;j+=i) solve(pow,j,j+i-1);
        pow++;
    }
}
int query(int l,int r){
    int u=logg[l^r];
    return std::max(cat[u][l],cat[u][r]); 
}
int main(){
    size=read(),q=read();
    for(int i=1;i<=size;i++) a[i]=read(); 
    build(size);
    while(q--){
        int l=read(),r=read();
        printf("%d\n",query(l,r));
    }
    return 0;
}