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

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

int n, m, v[100010], a, x;

void cautbin0(int low, int high, int x)
{
    while(low <= high){
       int m = (high + low )/2;
       if (v[m] <= x)
          low = m + 1;
        else high = m -1;
    }
    m = (high + low )/2;
    if (v[m] > x) m --;
    if (v[m] == x )
        fout << m << endl;
    else
        fout << "-1";

}
void  cautbin1 (int low, int high, int x)
{
    while(low < high){
        int m = (high + low )/2;
       if (v[m] <= x)
          low = m + 1;
        else high = m ;
    }
    m = (high + low )/2;
    if (v[m] > x) m--;
    fout <<  m << endl;
}
void cautbin2 (int low, int high, int x)
{

    while(low < high){
        int m =  (high + low )/2;;
       if (v[m] < x)
          low = m + 1;
        else high = m;
    }
    m = (high + low )/2;
    if (v[m] > x) m++;
    fout <<  m << endl;
}
int main()
{
    fin >> n ;
    for(int i = 1; i <= n; ++i)
        fin >> v[i];

    fin >> m;
    for(int i = 0; i < m; ++i)
    {

        fin >> a >> x;
        if(a == 0)
            cautbin0(1, n, x);
        if (a == 1)
            cautbin1(1, n, x);
        if (a == 2)
            cautbin2(1, n, x);
    }
    return 0;
}