#include <fstream>
#include <algorithm>
using namespace std;
int v[100005];
int main()
{
    ifstream fin("cautbin.in");
    ofstream fout("cautbin.out");
   int n,m,op,x;
   fin>>n;
   for(int i=1;i<=n;i++)
   {
       fin>>v[i];
   }
   fin>>m;
   for(int i=1;i<=m;i++)
   {
       fin>>op>>x;
       if(op==0)
       {
           int st=1,dr=n,mij,val=-1;
           while(dr>=st)
           {
               mij=st+(dr-st)/2;
               if(v[mij]<=x)
               {
                   if(v[mij]==x)
                   {
                       val=mij;
                   }
                   st=mij+1;
               }
               else if(v[mij]>x)
               {
                   dr=mij-1;
               }
           }
           fout<<val<<'\n';
       }
       else if(op==1)
       {
          int st=1,dr=n,mij,val=-1;
          while(dr>=st)
           {
               mij=st+(dr-st)/2;
               if(v[mij]<=x)
               {
                   val=mij;
                   st=mij+1;
               }
               else if(v[mij]>x)
               {
                   dr=mij-1;
               }
           }
           fout<<val<<'\n';
       }
        else if(op==2)
       {
            int st=1,dr=n,mij,val=-1;
          while(dr>=st)
           {
               mij=st+(dr-st)/2;
               if(v[mij]>=x)
               {
                   val=mij;
                   dr=mij-1;
               }
               else if(v[mij]<x)
               {
                   st=mij+1;
               }
           }
           fout<<val<<'\n';
       }
   }
    return 0;
}