#include <iostream>
#include <fstream>
using namespace std;

int main()
{
    ifstream cin ("cautbin.in");
    ofstream cout ("cautbin.out");
   int n,m,x,y,sol=-1,mij;
   cin>>n;
   int v[n+1];
   for(int i=1;i<=n;i++)
   {
       cin>>v[i];
   }
   cin>>m;
   int st=1,dr=n;
   for(int i=1;i<=m;i++)
   {
       cin>>y>>x;
       if(y==0)
       {
           while(st<=dr)
           {
               mij=(st+dr)/2;
               if(x>v[mij])
                 st=mij+1;
                else
                if(x<v[mij])
                dr=mij-1;
                else
                {
                    sol=mij;
                    st=mij+1;
                }
           }
       }
       if(y==1)
       {
           while(st<=dr)
           {
               mij=(st+dr)/2;
               if(x>=v[mij])
               {
                   sol=mij;
                   st=mij+1;
               }
               else
               dr=mij-1;
           }
       }
       if(y==2)
       {
           while(st<=dr)
           {
               mij=(st+dr)/2;
               if(x<=v[mij])
                  {
                      sol=mij;
                      dr=mij-1;
                  }
                  else
                  st=mij+1;
           }
       }
       cout<<sol<<"\n";
       sol=-1;
       st=1;dr=n;
   }
    return 0;
}