#include <iostream>
#include <fstream>

using namespace std;
ifstream f("cautbin.in" );
ofstream g("cautbin.out");

int NrElem, NrIntrebari, TipIntrebare, x;
int v[100001];

int Binary_Search0(int from, int to, int a[], int x) {
    int m = (from+to)/2;

    if ( !(from <= to) ) {
        if ( a[m] == x ) return m;
        return -1;
    }

    if ( x <  a[m] ) return Binary_Search0(from,  m-1, a, x);
    if ( x >= a[m] ) return Binary_Search0(m+1 ,   to, a, x);
}

int Binary_Search1(int from, int to, int a[], int x) {
    int m = (from+to)/2;

    if ( !(from < to) ) {
        if ( a[m] > x ) m--;
        return m;
    }

    if ( a[m] <= x ) return Binary_Search1(m+1, to, a, x);
    if ( a[m] >  x ) return Binary_Search1(from, m, a, x);
}

int Binary_Search2(int from, int to, int a[], int x) {
    int m = (from+to)/2;

    if ( !(from < to) ) {
        if ( v[m] < x ) m++;
        return m;
    }

    if ( x <= a[m] ) return Binary_Search2(from,  m, a, x);
    if ( x >  a[m] ) return Binary_Search2(m+1 , to, a, x);
}


int main() {
    f >> NrElem;

    for ( int i=1 ; i<=NrElem ; i++ )
        f >> v[i];

    f >> NrIntrebari;

    for ( int i=1 ; i<=NrIntrebari ; i++ ) {
        f >> TipIntrebare >> x;

        if ( TipIntrebare == 0 ) g << Binary_Search0(1, NrElem, v, x) << '\n';
        if ( TipIntrebare == 1 ) g << Binary_Search1(1, NrElem, v, x) << '\n';
        if ( TipIntrebare == 2 ) g << Binary_Search2(1, NrElem, v, x) << '\n';
    }
}