#include<bits/stdc++.h>
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int v[100001];
int cb0 (int p, int u, int key)
{ int m;
while(p<=u)
{ m=(p+u)/2;
if(v[m]<=key) p=m+1; else u=m-1;
}
m=(p+u)/2;
if(key<v[m]) --m;
if(key==v[m]) return m;
return -1;
}
int cb1(int p, int u, int key)
{ int m;
while(p<u)
{ m=(p+u)/2;
if(v[m]<=key) p=m+1; else u=m;
}
m=(p+u)/2;
if(key<v[m]) --m;
return m;
}
int cb2 (int p, int u, int key)
{ int m;
while(p<u)
{ m=(p+u)/2;
if(v[m]<key) p=m+1; else u=m;
}
m=(p+u)/2;
if(v[m]<key) ++m;
return m;
}
int main ()
{ int n,m,tip,val;
f >> n;
for(int i=1;i<=n;++i) f >> v[i];
f >> m;
while(m--)
{ f >> tip >> val;
if(tip==0) g << cb0(1,n,val) << '\n';
if(tip==1) g << cb1(1,n,val) << '\n';
if(tip==2) g << cb2(1,n,val) << '\n';
}
g.close();
f.close();
return 0;
}