#include <cstdio>

int v[100005],n,st,dr,mid;

int solve_0(int x)
{ int poz=-1;
    for(st=1,dr=n;st<=dr;)
    { mid=(st+dr)/2;
    if(v[mid]>x) dr=mid-1;
    else if(v[mid]<x) st=mid+1;
    else { poz=mid; st=mid+1; }
    }
return poz;
}

int solve_1(int x)
{ int poz=0;
    for(st=1,dr=n;st<=dr;)
    { mid=(st+dr)/2;
    if(v[mid]>x) dr=mid-1;
    else if(v[mid]<=x) { poz=mid; st=mid+1; }
    }
return poz;
}

int solve_2(int x)
{ int poz=0;
    for(st=1,dr=n;st<=dr;)
    { mid=(st+dr)/2;
    if(v[mid]>=x) { poz=mid; dr=mid-1; }
    else if(v[mid]<x) st=mid+1;
    }
return poz;
}

int main(){

    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);

int x,o,m,i;
    scanf("%d",&n);

for(i=1;i<=n;++i)
    scanf("%d",&v[i]);

scanf("%d",&m);

for(i=0;i<m;++i)
{ scanf("%d %d",&o,&x);
if(!o) printf("%d\n",solve_0(x));
else if(o==1) printf("%d\n",solve_1(x));
else if(o==2) printf("%d\n",solve_2(x));
}

return 0;
}