#include <fstream>

using namespace std;

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

int n, v[100005], m, i, x, q;

void cb0(int x){
    int p=1, u=n, mid;
    while(p <= u){
        mid = (p+u)/2;
        if(v[mid] <= x){
            p = mid+1;
        }else{
            u = mid-1;
        }
    }

    if(v[u] == x){
        fout<<u;
    }else{
        fout<<-1;
    }
}

void cb1(int x){
    int p=1, u=n, mid;
    while(p <= u){
        mid = (p+u)/2;
        if(v[mid] <= x){
            p = mid+1;
        }else{
            u = mid-1;
        }
    }
    fout<<u;
}

void cb2(int x){
    int p=1, u=n, mid;
    while(p <= u){
        mid = (p+u)/2;
        if(v[mid] >= x){
            u = mid-1;
        }else{
            p = mid+1;
        }
    }
    fout<<p;
}

int main() {


    fin>>n;
    for (i=1;i<=n;i++)
        fin>>v[i];

    fin >> m;
    for (i=1;i<=m;i++){
        fin>>q>>x;
        if(q == 0){
            cb0(x);
        }
        if(q == 1){
            cb1(x);
        }
        if(q == 2){
            cb2(x);
        }
        fout<<"\n";
    }
    return 0;
}