#include <fstream>

using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
const int NMAX = 100000;
int v[NMAX+5];
int cautare_binara1(int element, int n)
{
    int st = 1, dr = n, med;
    int solutie =-1;
    while(st<=dr)
    {
       med = (st + dr)>>1;
       if(v[med] == element)
       {
          solutie = med;
          st = med + 1 ;
          continue;
       }
       if(v[med] < element)
       {
           st = med +1;
           continue;
       }
       else
       {
           dr = med - 1 ;
           continue;
       }
    }
    return solutie;
}

int cautare_binara2(int element, int n)
{
    int st = 1, dr = n, med;
    int solutie =-1;
    while(st<=dr)
    {
       med = (st + dr)>>1;
       if(v[med] <= element)
       {
           st = med +1;
            solutie = med;
           continue;
       }
       else
       {
           dr = med - 1 ;
           continue;
       }
    }
    return solutie;
}

int cautare_binara3(int element, int n)
{
    int st = 1, dr = n, med;
    int solutie =-1;
    while(st<=dr)
    {
       med = (st + dr)>>1;
       if(v[med] >= element)
       {
          solutie = med;
          dr = med - 1 ;
          continue;
       }
       else
       {
           st = med +1;
           continue;
       }
    }
    return solutie;
}

int main()
{
    int n, i, k, x, m;
    fin>>n;
    for(i=1;i <= n; i++)
    {
       fin>>v[i];
    }
    fin>>m;
    for(i=1;i <= m ;i++)
    {
       fin>>k>>x;
       if(k ==0)
       {
           fout<<cautare_binara1(x, n)<<"\n";
           continue;
       }
       if(k==1)
       {
          fout<<cautare_binara2(x, n)<<"\n";
          continue;
       }
       if(k==2)
       {
           fout<<cautare_binara3(x, n)<<"\n";
           continue;
       }
    }
    return 0;
}