#include<cstdio>
#define NMAX 100001
 
int v[NMAX];
int i,j,n,k,op,nr,m;
 
void cautare0(int x)
{
    int st=1,dr=n,mid;
 
    while (st <= dr) {
        mid = (st + dr) / 2;
        if (v[mid] <= x)
            st = mid + 1;
        else
            dr = mid - 1;
    }
    mid = (st + dr) / 2;
  
    if (v[mid] > x) mid --;
    if (v[mid] == x)
        printf("%d",mid);
    else printf("-1");
}
 
void cautare1(int x)
{
int st=1,dr=n;
int mid;
mid=st+(dr-st)/2;
while(st<dr)
{
 if(v[mid]<=x) st=mid+1;
 else
    dr=mid-1;
 mid=st+(dr-st)/2;
 
}
if(v[mid]>x) mid--;
printf("%d\n",mid);
 
}
 
 
void cautare2(int x)
{
    int st=1,dr=n;
    int mid;
    mid=st+(dr-st)/2;
    while(st<dr)
    {
        if(v[mid]<x) st=mid+1;
        else
            dr=mid-1;
        mid=st+(dr-st)/2;
    }
 
if(v[mid]<x) mid++;
printf("%d\n",mid);
}
 
int main()
{
 
freopen("cautbin.in","r",stdin);
freopen("cautbin.out","w",stdout);
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d",&v[i]);
scanf("%d",&m);
for(i=1;i<=m;i++)
{
    scanf("%d%d",&op,&nr);
    switch(op)
    {
        case 0:{cautare0(nr); break;}
        case 1:{cautare1(nr); break;}
        case 2:{cautare2(nr); break;}
    }
 
}
    return 0;
}