#include<fstream>
#define Max 100001

using namespace std;


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

long a[Max],n,m;
int bs(long x)
{
    int lo,hi,mid;
    lo = 1; hi = n;
    while(lo <= hi)
    {
             mid = lo +(hi - lo)/2;
             if(x < a[mid])hi = mid-1;
             else if(x > a[mid])lo = mid+1;
             else return mid;
    }
return -1;
}
int bs1(long x)
{
    int lo,hi,mid,val;
    lo = 1;hi = n;
    while(lo <= hi)
    {
             mid = lo +(hi - lo)/2;
             if(x >= a[mid])
             {
                  val = mid;
                  lo = mid+1;
             }
             else hi = mid-1;
    }
    return val;
}
int bs2(long x)
{
    int hi,lo,mid,val;
    lo = 1;
    hi = n;
    while(lo <= hi)
    {
               mid = lo +(hi - lo)/2;
         if(x <= a[mid])
         {
              val = mid;
              hi = mid-1;
         }
         else lo = mid+1;
    }
    return val;
}
int main()
{
    int i,c;
    long b;
    fin>>n;
    for(i = 1; i <= n; i++)
    fin>>a[i];
    fin>>m;
    for(i = 1; i <= m; i++)
    {
          fin>>c>>b;
          if(c == 0)
          fout<<bs(b)<<"\n";
          if(c == 1)
          fout<<bs1(b)<<"\n";
          if(c==2)
          fout<<bs2(b)<<"\n";
    }
fin.close();
fout.close();
return 0;
}