#include <cstdio>
using namespace std;int bin0(int *v,int x,int lo,int hi){int mid;while(lo<=hi){mid=lo+(hi-lo)/2;if(v[mid]<=x)lo=mid+1;else hi=mid-1;}if(v[mid]>x)mid--;if(v[mid]==x)return mid;return -1;}int bin1(int *v,int x,int lo,int hi){int mid;while(lo<hi){mid=lo+(hi-lo)/2;if(v[mid]<=x)lo=mid+1;else hi=mid;}mid=lo+(hi-lo)/2;if(v[mid]>x) mid--;return mid;}int bin2(int *v,int x,int lo,int hi){int mid;while(lo<hi){mid=lo+(hi-lo)/2;if(v[mid]<x)lo=mid+1;else hi=mid;}mid=lo+(hi-lo)/2;if(v[mid]<x)mid++;return mid;}int main(){freopen("cautbin.in","r",stdin);freopen("cautbin.out","w",stdout);int n;scanf("%d",&n);int*v;v=new int[n];for(int i=1;i<=n;i++)scanf("%d",&v[i]);int m;scanf("%d",&m);while(m--){int a,x;scanf("%d%d",&a,&x);if(a==0)printf("%d\n",bin0(v,x,1,n));if(a==1)printf("%d\n",bin1(v,x,1,n));if(a==2)printf("%d\n",bin2(v,x,1,n));}}