#include<fstream>
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
long n,m,v[100001],i,j,a;
bool ok=0;
short x;
long caut_binar(long st,long dr,long a)
{ok=0;
 while(ok==0&&st<dr)
   {m=(st+dr)/2;
    if(v[m]==a)
      {if(x==0||x==1)
         while(v[m]==v[m+1])
            m++;
       else
         if(x==2)
           while(v[m]==v[m-1])
             m--;
        ok=1;
        return m;
      }
    else
      if(v[m]>a)
        dr=m-1;
      else
        st=m+1;
   }
 if(ok==0)
   {
    if(x==0)
        return -1;
    else
     if(x==1)
        {if(v[m]<a)
           while(v[m+1]<a)
              m++;
         else
            while(v[m]>a)
              m--;
         return m;
        }
     else
       if(x==2)
         {if(v[m]<a)
          {while(v[m]<=a)
             m++;
            return m;
          }
         else
           {while(v[m-1]==v[m])
              m--;
            return m;
           }
         }
   }
}
int main()
{f>>n;
 for(i=1;i<=n;i++)
    f>>v[i];
 f>>m;
 for(i=1;i<=m;i++)
  {
    f>>x>>a;
    g<<caut_binar(1,n,a)<<'\n';

  }
f.close();g.close();
return 0;
}