#include <cstdio>
using namespace std;
int n,v[100020],up,down,mid,log;
int cautare(int x)
{
     int lo=1,hi=n;
    while(lo<=hi)
    {
        mid=(lo+hi)/2;
        if(v[mid]<=x)
        {
            lo=mid+1;
        }
        else
        {
            hi=mid-1;
        }
    }
    return hi;
}



int main()
{
    int h,i,a,b,m;
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);
    scanf("%d",&k);
    for(i=1;i<=k;++i)
    {
        scanf("%d",&v[i]);
    }

    scanf("%d",&m);

    for(i=1;i<=m;++i)
    {
        scanf ("%d %d",&a,&b);
       if(a==1)
       {
           printf("%d \n",cautare(b));
       }
       else if(a==2)
       {
           printf("%d \n",cautare(b-1)+1);
       }
       else
       {
           h=cautare(b);
           if(v[h]==b)
           {
               printf("%d \n",cautare(b));
           }
           else
           {
               printf("-1 \n");
           }
       }


    }
    return 0;
}