#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';
        }
     }
//cout<<sizeof(a)/1024.0/1024.0;
fin.close();
fout.close();

    return 0;
}