#include <cstdio>

using namespace std;
int a[100009],n,i,m,t,x;

int caut0(int x)
{
   int mj,p=1,u=n;

   while(p<=u)
   {
     mj=(p+u)/2;
     if(a[mj]<=x) p=mj+1;
     else u=mj-1;
   }

   if(a[u]==x) return u;
   else return -1;

}

int caut1(int x)
{
   int mj,p=1,u=n;

   while(p<=u)
   {
     mj=(p+u)/2;
     if(a[mj]<=x) p=mj+1;
     else u=mj-1;
   }

   return u;

}

int caut2(int x)
{
   int mj,p=1,u=n;

   while(p<=u)
   {
     mj=(p+u)/2;
     if(a[mj]<x) p=mj+1;
     else u=mj-1;
   }

   return p;

}


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

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

    scanf("%d",&m);

    for(i=1;i<=m;++i)
    {
       scanf("%d%d",&t,&x);
       if(t==0)
       printf("%d\n",caut0(x));
       else if(t==1)
       printf("%d\n",caut1(x));
       else printf("%d\n",caut2(x));

    }






    return 0;
}