#include<iostream>
#include<cstring>
using namespace std;
const int N=1919810;
typedef long long ll;
ll n,m;
ll a[N];
ll st1[N][25];
ll ans1,ans2;
ll lg[N];

int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
       scanf("%lld",&a[i]); 
       st1[i][0]=a[i];
    } 

    for(int i=1;i<22;i++){
        for(int j=1<<i;j<N&&j<(1<<i+1);j++) lg[j]=i;
    }
    for(int j=1;j<20;j++){
        for(int i=1;i<=n;i++){
            st1[i][j]=max(st1[i][j-1],st1[i+(1<<(j-1))][j-1]);

        }
    }
    cin>>m;
    while(m--){
        int l,r;
        scanf("%d%d",&l,&r);
        ll t=lg[r-l+1];
        ans1=max(st1[l][t],st1[r-(1<<t)+1][t]);
        cout<<ans1<<"\n";
    }

}

#include<iostream>
#include<set>
#include<cstring>
using namespace std;
const int N=114514;
int h[N],e[N],idx,ne[N];
int n,m,k;
int f[N],rd[N];
void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

int sg(int x){
    if(f[x]!=-1) return f[x];
    set<int> s;
    for(int i=h[x];~i;i=ne[i]){
        int j=e[i];
        s.insert(sg(j));
    }
    int i=0;
    while(1){
        if(!s.count(i)) return f[x]=i;
        i++;
    }
}

int main(){
    cin>>n>>m>>k;
    memset(h,-1,sizeof h);
    for(int i=1;i<=m;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b);
        rd[a]++;
    }
    memset(f,-1,sizeof f);
    for(int i=1;i<=n;i++) if(rd[i]==0) f[i]=0;
    int ans=0;
    for(int i=1;i<=k;i++){
        int u;
        scanf("%d",&u);
        ans^=sg(u);
    }
   // for(int i=1;i<=n;i++)  cout<<f[i]<<" ";
    if(ans==0) puts("lose");
    else puts("win");

}

#include<iostream>
using namespace std;
const int N=114514,mod=5000011;
typedef long long ll;
ll a[N];
int n,k;
int main(){
    cin>>n>>k;
    a[0]=1;
    for(int i=1;i<=n;i++){
        if(i>=k+2)a[i]=a[i-k-1];
        else a[i]=1;
        a[i]+=a[i-1];
        a[i]%=mod;
    }
    //for(int i=0;i<=n;i++) cout<<a[i]<<" ";
    //cout<<endl;
    cout<<a[n]<<endl;
}

#include<iostream>
using namespace std;
const int N=114514;
int a[N],f[N],dp[10];
int ans;

int getnum(int x){
    while(x>=10) x/=10;
    return x;
}
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++){
        int x=getnum(a[i]),t=a[i]%10;
        f[i]=dp[x]+1;
        dp[t]=max(dp[t],dp[x]+1);
        ans=max(ans,f[i]);
    }
    cout<<n-ans<<endl;
}

#include<iostream>
#include<cstring>
using namespace std;
//卡常大师ACWING
const int N=514,INF=0x3f3f3f3f;
int d[N][N],g[N][N];
int n;
int ans;

void print(){
    for(int j=1;j<=n;j++){
            for(int k=1;k<=n;k++){
                if(d[j][k]>INF/2) printf("INF ");
             else   printf("%d ",d[j][k]);
            }
            cout<<endl;
        }
        cout<<endl;
}

void floyd(){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            for(int k=1;k<=n;k++){
                d[j][k]=min(d[j][i]+d[i][k],d[j][k]);
            }
        }
    }
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++) scanf("%d",&g[i][j]);
    }
    memset(d,0x3f,sizeof d);
    for(int i=1;i<=n;i++) d[i][i]=0;
    for(int i=n;i>=1;i--){
        int res=0;
        for(int j=i+1;j<=n;j++){
            for(int k=j;k<=n;k++){
               if(d[j][k]<INF/2) res+=d[j][k];
            }
        }
        ans+=res*2;
        for(int j=n;j>=1;j--) d[i][j]=min(g[i][j],d[i][j]),d[j][i]=min(g[j][i],d[j][i]);




        for(int j=1;j<=n;j++){
            for(int k=1;k<=n;k++){
                d[j][k]=min(d[j][k],d[j][i]+d[i][k]);
            }
        }
        //floyd();
        //print();
        //cout<<ans<<endl;
    }
    cout<<ans<<endl;
}

#include<iostream>
#include<algorithm>
using namespace std;
typedef pair<int,string> PIS;
const int N=114514;
PIS a[N];

int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        int x;
        string s;
        cin>>x>>s;
        a[i]={x,s};
    }
    sort(a+1,a+1+n);
    for(int i=n;i>=1;i--) cout<<a[i].second<<endl;
}

#include<iostream>
using namespace std;
string s;

int main(){
    bool tf=0;
    while(getline(cin,s)){
        if(s=="ENDOFINPUT") break;
        string str;
        bool flag=0;
        getline(cin,str);
        for(int i=0;i<str.size();i++){
            int t=str[i]-'A';
            t=(t+21)%26;
            if(str[i]>='A'&&str[i]<='Z') str[i]='A'+t;
        }
        cout<<str<<endl;
        getline(cin,s);
    }
}

#include<iostream>
#include<cstring>
using namespace std;
const int N=1145;
int f[N][N];
int cnt[N];
int a[N];
int n;

int main(){
    int t;
    cin>>t;
    while(t--){
        int t=0;
        memset(f,0,sizeof f);
        memset(cnt,0,sizeof cnt);
        cin>>n;
        for(int i=1;i<=n;i++){
           scanf("%d",&a[i]);
           cnt[a[i]]++;
        } 
        for(int i=1;i<=n;i++){
            int k;
            cin>>k;
            t=max(t,k);
            f[k][a[i]]++;
        }
        for(int i=1;i<=t;i++){
            bool flag=0;
            for(int j=1;j<=1000;j++){
                if(cnt[j]){
                    if(flag==0){
                        flag=1;
                        printf("%d={",i);
                    }else{
                        printf(",");
                    }
                    printf("%d=%d",j,f[i][j]);
                }
            }
            if(flag){
               printf("}");
            printf("\n"); 
            } 
        }
    }
}