#include <bits/stdc++.h>

using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int v[100002];
int cb0(int st, int dr, int x){
    int med, poz = -1;
    while(st <= dr){
        med = (st + dr) >> 1;
        if(v[med] == x){
            poz = med;
            st = med + 1;
        }
        else if(v[med] < x) st = med + 1;
        else dr = med - 1;
    }
    return poz;
}
int cb1(int st, int dr, int x){
    int med, poz;
    while(st <= dr){
        med = (st + dr) >> 1;
        if(v[med] <= x){
            poz = med;
            st = med + 1;
        }
        else dr = med - 1;
    }
    return poz;
}
int cb2(int st, int dr, int x){
    int med, poz;
    while(st <= dr){
        med = (st + dr) >> 1;
        if(v[med] >= x){
            poz = med;
            dr = med - 1;
        }
        else st = med + 1;
    }
    return poz;
}
int main()
{
    int n,i,q,c,x;
    fin >> n;
    for(i = 1; i <= n; i++) fin >> v[i];
    fin >> q;
    while(q--){
        fin >> c >> x;
        if(!c) fout << cb0(1,n,x) << "\n";
        else if(c == 1) fout << cb1(1,n,x) << "\n";
        else fout << cb2(1,n,x) << "\n";
    }
    return 0;
}