#include <cstdio>

using namespace std;
int n,i,tot,v[100005],x,cer;
int caut0(int stg,int dr,int val)
{
    int mij;
    int poz;
    while(stg<=dr)
    {
        mij=(stg+dr)/2;
        if(v[mij]<=val)
        {
            poz=mij;
            stg=mij+1;
        }
        else
            dr=mij-1;
    }
    if(v[poz]==val)
        return poz;
    return -1;
}
int caut1(int stg,int dr,int val)
{
    int mij;
    int poz;
    while(stg<=dr)
    {
        mij=(stg+dr)/2;
        if(v[mij]<=val)
        {
            poz=mij;
            stg=mij+1;

        }
        else
            dr=mij-1;
    }
    return poz;
}
 int caut2( int stg, int dr, int val)
 {
     int mij;
     int poz;
     while(stg<=dr)
     {
         mij=(stg+dr)/2;
         if(v[mij]<val)
            stg=mij+1;
         else
         {
             poz=mij;
             dr=mij-1;
         }
     }
     return poz;
 }
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 ",&tot);
    for(i=1;i<=tot;i++)
    {
        scanf("%d %d ",&cer,&x);
        if(cer==0) printf("%d\n",caut0(1,n,x));
        else
            if(cer==1) printf("%d\n",caut1(1,n,x));
        else
            printf ("%d\n",caut2(1,n,x));
    }

    return 0;
}