#include<fstream>
#define lmax 110000
using namespace std;
int n,v[lmax],op,x;
int caut(int st,int dr){
    if(st>dr)return st;
    int m=st+(dr-st)/2;
    if(x>=v[m])return caut(m+1,dr);
    else return caut(st,m-1);
}
int cautf(int st, int dr){
    if(st>dr)return st;
    int m=st+(dr-st)/2;
    if(x>v[m])return caut(m+1,dr);
    else return caut(st,m-1);
}
int main(){
    int i,et,b;
    ifstream f("cautbin.in");
    ofstream g("cautbin.out");
    f>>n;
    for(i=1;i<=n;i++)
        f>>v[i];
    f>>et;
    while(et!=0){et--;
        f>>op>>x;
        if(op!=2)b=caut(1,n);
        else b=cautf(1,n);
        if(op==0){
             if(v[b-1]!=x)g<<-1;
             else g<<b-1;
        }
        if(op==1)g<<b-1;
          if(op==2){
            if(v[b-1]!=x)
                {if(b==n+1)g<<b-1;
                    else g<<b;}
		else if(v[b-1]<x&&b<=n)g<<b;
			else g<<b-1;}
        g<<'\n';}
    f.close();
}