#include <fstream>

using namespace std;
const int MAX=100006;

int n,m,v[MAX],cod,x;

ifstream in("cautbin.in");
ofstream out("cautbin.out");
int cautbinar0()
{
   int st=1,dr=n,ind=-1;
   int m;
   while(st<dr)
   {
       m=(st+dr)/2;
       if(v[m]<x)
       {
            dr=m-1;
       }

       else st=m+1;

       if(v[m]==x)
       {
           ind=m;

       }

   }

   return ind;


}

int cautbinar1()
{
   int st=1,dr=n,ind=-1;
   int m;
   while(st<dr)
   {
       m=(st+dr)/2;
       if(v[m]<x)
       {
            dr=m-1;
       }

       else st=m+1;

       if(v[m]==x)
       {
           ind=m;

       }

   }

   if(v[st]<v[dr]) return st;
   else return dr;


}

int cautbinar2()
{
   int st=1,dr=n;
   int m;
   while(st<dr)
   {
       m=(st+dr)/2;
       if(v[m]<x)
       {
            dr=m-1;
       }

       else st=m+1;

       if(v[m]==x)
       {
           return m;

       }

   }

   if(v[st]>v[dr]) return st;
   else return dr;


}
int main()
{
    in>>n;

    for(int i=1;i<=n;i++) in>>v[i];

    in>>m;

    for(int i=1;i<=m;i++)
    {
       in>>cod>>x;
       if(cod==0)
       {

             out<<cautbinar0()<<"\n";
       }

       if(cod==1)
       {
            out<<cautbinar1()<<"\n";

       }

       if(cod==2)
       {
           out<<cautbinar2()<<"\n";


       }

    }
    return 0;
}