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

ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

int main()
{
   unsigned int n,m,i,s,d,mij,tip,x;
   unsigned int a[100001];
   fin>>n;
   for(i=1; i<=n; i++) fin>>a[i];
   fin>>m;
   for(i=1; i<=m; i++)
     {fin>>tip>>x;
      if(tip==0)
        {s=1; d=n;
         while (s<=d)
             {mij=(s+d)/2;
              if(a[mij]<=x) s=mij+1;
              else d=mij-1;
             }
         if(a[mij]>x) mij--;
         if(a[mij]==x) fout<<mij<<"\n";
         else fout<<"-1"<<"\n";
        }
       if(tip==1)
            {s=1; d=n;
             while (s<d)
                {mij=(s+d)/2;
                 if(a[mij]<=x) s=mij+1;
                 else d=mij;
                }
             mij=(s+d)/2;
             if(a[mij]>x) fout<<mij-1<<"\n";
             else fout<<mij<<"\n";
            }
        if(tip==2)
            {s=1; d=n;
             while (s<d)
                {mij=(s+d)/2;
                 if(a[mij]<x) s=mij+1;
                 else d=mij;
                }
             mij=(s+d)/2;
             if(a[mij]<x) fout<<mij+1<<"\n";
             else fout<<mij<<"\n";
            }
     }
    fin.close();
    fout.close();
    return 0;
}