#include<iostream>
#include<fstream>
using namespace std;
ifstream in("rmq.in");
ofstream out("rmq.out");
const int NMAX=100007,LOGMAX=17,MOD=1000000007;
int n,q,rmq[LOGMAX+1][2*NMAX];
int i,it,op,logn,a,b;
int po[24];
int pomod[NMAX],ras,logg[2*NMAX];
long long ll;
int aux,len;
int main()
{
    in>>n;
    pomod[0]=1;
    for(i=1;i<=n;i++)
    {
        ll=(long long)(2*pomod[i-1]);
        pomod[i]=int(ll%MOD);
    }
    op=1;
    logn=0;
    while(op<=n)
    {
        po[logn]=op;
        op*=2;
        logn++;
    }
    logn--;
    op=1;
    aux=0;
    while(op<=n)
    {
        for(i=op;i<2*op;i++)
        {
            logg[i]=aux;
        }
        aux++;
        op*=2;
    }
    for(i=1;i<=n;i++)
    {
        cin>>a;
        rmq[0][i]=-a;
    }
    for(it=1;it<=logn;it++)
    {
        for(i=1;i<=n;i++)
        {
            rmq[it][i]=max(rmq[it-1][i],rmq[it-1][i+po[it-1]]);
        }
    }
    in>>q;
    for(i=1;i<=q;i++)
    {
        in>>a>>b;
        len=logg[b-a+1];
        ras=max(rmq[len][a],rmq[len][b+1-po[len]]);
        ll=(long long)(ras*pomod[b-a]);
        //ras=int(ll%MOD);
        out<<-ras;
    }
}