#include <fstream>

using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int n,m,x,y,i,a[100005],st,dr,med,r;
int main()
{
    f>>n;
    for(i=1;i<=n;i++)
        f>>a[i];
    f>>m;
    while(m!=0){
        f>>x>>y;
        st=1;
        dr=n;
        if(x==0 || x==1){
            while(st<=dr){
                med=(st+dr)/2;
                if(a[med]<=y){
                    r=med;
                    st=med+1;
                }
                else
                    dr=med-1;
            }
            if(x==0){
                if(a[r]==y)
                    g<<r<<"\n";
                else
                    g<<"-1"<<"\n";
            }
            if(x==1)
                g<<r<<"\n";
        }
        if(x==2){
            while(st<=dr){
                med=(st+dr)/2;
                if(a[med]>=y){
                    r=med;
                    dr=med-1;
                }
                else
                    st=med+1;
            }
            g<<r<<"\n";
        }
        m--;
    }
    return 0;
}