#include <bits/stdc++.h>
using namespace std;
#if 1
#define cin fin
#define cout fout
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
#endif // 1
int n;
const int nmx = 1e5 + 4;
int a[nmx];
// cea mai mare pozitie pe care se afla un element cu valoarea x sau -1 daca aceasta valoare nu se gaseste in sir (upper_bound)
int cb0(int x){
    int st=1,dr=n+1;
    int p = -1;
    while(st<=dr){
        int md = (st+dr)/2;
        if(a[md]<=x){
            p = md;
            st = md + 1;
        }
        else
            dr = md - 1;
    }
    if(a[p]!=x)
        return -1;
    else
        return p;
}

//cea mai mare pozitie pe care se afla un element cu valoarea mai mica sau egala cu x in sir.
//Se garanteaza ca cel mai mic numar al sirului este mai mic sau egal decat x (upper_bound)

int cb1(int x){
    int st=1,dr=n+1;
    int p = -1;
    while(st<=dr){
        int md = (st+dr)/2;
        if(a[md]<=x){
            p = md;
            st = md + 1;
        }
        else
            dr = md - 1;
    }
    return p;
}

// cea mai mica pozitie pe care se afla un element cu valoarea mai mare sau egala cu x in sir.
// Se garanteaza ca cel mai mare numar din sir este mai mare sau egal decat x (lower_bound)

int cb2(int x){
    int st=1,dr=n+1;
    int p = -1;
    while(st<=dr){
        int md = (st+dr)/2;
        if(a[md]>=x){
            p = md;
            dr = md - 1;
        }
        else
            st = md + 1;
    }
    return p;
}

int main(){
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> a[i];
    }
    int m;
    cin >> m;
    while(m--){
        int op,x;
        cin >> op >> x;
        if(op==0){
            cout << cb0(x) << "\n";
        }
        else if(op==1){
            cout << cb1(x) << "\n";
        }
        else if(op==2){
            cout << cb2(x) << "\n";
        }
    }
}