#include <fstream>

#include <cstdlib>

#define NMAX 100002

using namespace std;

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

int n, m, tip, nr;
int v[NMAX];

int cb0(int nr);
int cb1(int nr);
int cb2(int nr);

int main()
{
    int i;
    fin>>n;;
    for(i = 1; i <= n; i++) fin>>v[i];
    fin>>m;
    for(i = 1; i <= m; i++)
       {
        fin>>tip>>nr;
        if(tip == 0)
          fout<<cb0(nr)<<'\n';
          else
          if(tip == 1)
             fout<<cb1(nr)<<'\n';
             else
             fout<<cb2(nr)<<'\n';
       }
    return 0;
}

int cb0(int nr)
{
 int st = 0, dr = n + 1, mij;
 while(dr - st > 1)
    {
     mij = (st + dr) / 2;
     if(v[mij] <= nr)
       st = mij;
       else
       dr = mij;
    }
 if(v[st] != nr) return -1;
 return st;
}

int cb1(int nr)
{
 int st = 0, dr = n + 1, mij;
 while(dr - st > 1)
    {
     mij = (st + dr) / 2;
     if(v[mij] <= nr)
       st = mij;
       else
       dr = mij;
    }
 return st;
}

int cb2(int nr)
{
 int st = 0, dr = n + 1, mij;
 while(dr - st > 1)
    {
     mij = (st + dr) / 2;
     if(v[mij] < nr)
       st = mij;
       else
       dr = mij;
    }
 if(v[st] != nr) return st + 1;
 return st;
}