#include<fstream>
using namespace std;
long n,m,i,mij; unsigned long v[100001],c,x;
ifstream f1("cautbin.in"); ofstream f2("cautbin.out");

void read(){f1>>n; for(i=1;i<=n;i++) f1>>v[i]; f1>>m;}

int task0(long p,long u,unsigned long q){int ok;
if(p==1&&u==n) ok=0; if(v[mij]==q&&v[mij+1]!=q) return mij;
if(p>u) return -1; mij=(p+u)/2;
if(v[mij]==q) {ok=1; return task0(mij+1,u,q);}
if(v[mij]>q) return task0(p,mij-1,q);
if(v[mij]<q) return task0(mij+1,u,q);}

int task1(long p,long u,unsigned long q){int ok;
if(p==1&&u==n) ok=0; if(p>u) return mij; mij=(p+u)/2;
if(v[mij]<=q){ok=1; return task1(mij+1,u,q);}
if(ok&&v[mij]>q) {while(v[mij]>q) mij--; return mij;}
if(v[mij]>q) return task1(p,mij-1,q);
if(v[mij]<q) return task1(mij+1,u,q);}

int task2(long p,long u,unsigned long q){int ok;
if(p==1&&u==n) ok=0; ; mij=(p+u)/2;
if(v[mij]<q&&ok) {while(v[mij]<q) mij++; return mij;}
if(v[mij]<q) return task2(mij+1,u,q);
if(v[mij]>=q) {ok=1; return task2(p,mij-1,q);}}

int main(){read(); for(i=1;i<=m;i++) {f1>>c>>x; if(c==0) f2<<task0(1,n,x)<<'\n';
if(c==1) f2<<task1(1,n,x)<<'\n'; if(c==2) f2<<task2(1,n,x)<<'\n';}
f1.close(); f2.close(); return 0;}