#include <fstream>
//Imi urasc viata
using namespace std;

ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

#define NMAX 100001

int V[NMAX],n,k;

int CB1(int s, int d){
    int sol,m;
while(s<=d){
    m=(s+d)/2;
        if(V[m]<=k)
            {
                if(V[m]==k)
                    sol=k;
                s=m+1;
            }
        else
            d=m-1;
}
 return sol;
}

int CB2(int s,int d){
int sol,m;
while(s<=d){
m=(s+d)/2;
    if(V[m]<=k){
        sol=k;
        s=m+1;
    }
    else
        d=m-1;
}
return sol;
}

int CB3(int s,int d){
    int sol,m;
while(s<=d){
m=(s+d)/2;
    if(V[m]>=k){
        sol=k;
        d=m-1;
    }
    else
        s=m+1;
}
return sol;

}

int main(){
    int Z,X;
    fin>>n;
    for(int i=1;i<=n;i++)
        fin>>V[i];
    fin>>Z;
    while(Z--)
    {
        fin>>X>>k;
        if(X==0)
            fout<<CB1(1,n)+1<<"\n";
        if(X==1)
            fout<<CB2(1,n)+1<<"\n";
        if(X==2)
            fout<<CB3(1,n)-1<<"\n";
    }
    return 0;
}