#include<cstdio>
int v[100001];
int main()
{
 int n,i,m,tip,x,st,dr,poz,pp,mij;
 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",&tip,&x);
     if(tip==0)
        {
         st=1;
         dr=n;
         poz=0;
         pp=0;
         while(st<=dr)
              {
               mij=(st+dr)/2;
               if(v[mij]<=x)
                  {
                   if(v[mij]==x)
                      pp=1;
                   poz=mij;
                   st=mij+1;
                  }
               else
                  {
                   dr=mij-1;
                  }
              }
         if(pp==1)
            printf("%d\n",poz);
         else
            printf("-1\n");
        }
     if(tip==1)
        {
         st=1;
         dr=n;
         poz=0;
         pp=0;
         while(st<=dr)
              {
               mij=(st+dr)/2;
               if(v[mij]<=x)
                  {
                   poz=mij;
                   st=mij+1;
                   pp=1;
                  }
               else
                  {
                   dr=mij-1;
                  }
              }
         if(pp==1)
            printf("%d\n",poz);
        }
     if(tip==2)
        {
         st=1;
         dr=n;
         poz=0;
         pp=0;
         while(st<=dr)
              {
               mij=(st+dr)/2;
               if(v[mij]>=x)
                  {
                   poz=mij;
                   dr=mij-1;
                   pp=1;
                  }
               else
                  {
                   st=mij+1;
                  }
              }
         if(pp==1)
            printf("%d\n",poz);
        }
    }
return 0;
}