#include <fstream>

using namespace std;

ifstream cin("cautbin.in");
ofstream cout ("cautbin.out");

int n,m,v[100001];
int main(){
    cin >> n;
    for (int i =1; i <=n;++i)
        cin >> v[i];
    cin >> m;
    for (int i =1 ; i <=m;++i){
        int p,x,poz = -1;
        cin >> p >> x;
        int st = 1, dr = n;
        if (p == 0){

            while (st <=dr){
                int mij = (st+dr)/2;
                if (v[mij] == x){
                    poz = mij;
                    st = mij +1;
                }
                if (v[mij] > x)
                    dr = mij-1;
                if (v[mij] < x)
                    st = mij+1;
            }
        }
        if (p==1){

            while (st <=dr){

                int mij = (st+dr)/2;
                if (v[mij] <= x){
                     poz = mij;
                     st = mij +1;
                }
                else
                    dr = mij-1;
                }
        }

        if (p == 2){
            while (st <=dr){

                int mij = (st+dr)/2;
                if (v[mij] >= x){
                     poz = mij;
                     dr = mij-1;
                }
                else
                    st = mij+1;
                }
        }
        cout << poz << "\n";
    }
}