#include <cstdio>
using namespace std;
int n,v[100020],hi,lo,mid;
int cautbin(int b)
{
     lo=1;
     hi=n;
            while(lo<=hi){

            mid=(hi+lo)/2;
            if(b>=v[mid])
            {
                lo=mid+1;
            }
            else
            {
                hi=mid-1;
            }
            }
            return hi;
}

int main()
{
    int h,i,j,k,a,b,m;
    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 ",&a,&b);
       if(a==1)
       {
           printf("%d \n",cautbin(b));
       }
       else if (a==2)
       {
           printf("%d \n",cautbin(b-1)+1);
       }
       else
       {
           h=cautbin(b);
           if(v[h]==b)
           {
               printf("%d \n",h);
           }
           else
           {
               printf("-1");
           }
       }


    }
    return 0;
}