#include<cstdio>
using namespace std;
int v[100010];
int main(){
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);
    int n,m,i,l1,l2,mij,tip,x,elem;
    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",&tip,&x);
        l1=1;
        l2=n;
        if(tip==1||tip==0)
            elem=-1;
        if(tip==2)
            elem=10000000;
        while(l1<=l2){
            mij=(l1+l2)/2;
            if(v[mij]==x&&tip==0&&mij>elem)
                elem=mij;
            if(v[mij]>=x&&mij<=elem&&tip==2)
                elem=mij;
            if(v[mij]<=x&&tip==1&&mij>=elem)
                elem=mij;
            if(v[mij]<x)
                l1=mij+1;
            if(v[mij]>x)
                l2=mij-1;
            if(v[mij]==x&&(tip==1||tip==0))
                l1=mij+1;
            if(v[mij]==x&&tip==2)
                l2=mij-1;
        }
        printf("%d\n",elem);
    }
    return 0;
}