#include <fstream>

using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int v[100005];
int n;
int op0(int n,int x)
{ int st=1,dr=n,mij;
    while(st<dr){
        mij=(st+dr)/2;
        if(v[mij]<x)
            st=mij+1;
        else
            dr=mij;
    }
  for(;st<n && v[st]==x;++st);
    if(v[st]>x)
        --st;
    if(v[st]!=x)
        return -1;
    return st;

}
int op1(int n,int x){
    int st=1,dr=n,mij;
    while(st<dr){
        mij=(st+dr+1)/2;
        if(v[mij]>x)
            dr=mij-1;
        else
            st=mij;

    }
    return st;
}
int op2(int n,int x){
    int st=1,dr=n,mij;
    while(st<dr){
        mij=(st+dr)/2;
        if(v[mij]<x)
            st=mij+1;
        else
            dr=mij;
    }
    return st;

}
int main ()
{ int x,m,i,op;
    f>>n;
    for(i=1;i<=n;i++)f>>v[i];
    f >>m;
    for(i=1;i<=m;i++){
        f >>op>>x;
        if(op==0)
            g<<op0(n,x)<<'\n';
        if(op==1)
            g<<op1(n,x)<<'\n';
        if(op==2)
            g<<op2(n,x)<<'\n';
    }
    return 0;
}