#include<bits/stdc++.h>
using namespace std;

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

int n, m, v[100005];

int q1(int x){
    int poz = -1, st = 1, dr = n;

    for(;st <= dr;){
        int m = st + dr >> 1;

        if(v[m] <= x){
            if(v[m] == x)
                poz = m;
            st = m + 1;
        }
        else
            dr = m - 1;
    }
    return poz;
}

int q2(int x){
    int poz = -1, st = 1, dr = n;

    for(;st <= dr;){
        int m = st + dr >> 1;

        if(v[m] <= x){
            poz = m;
            st = m + 1;
        }
        else
            dr = m - 1;
    }
    return poz;
}


int q3(int x){
    int poz = -1, st = 1, dr = n;

    for(;st <= dr;){
        int m = st + dr >> 1;

        if(v[m] >= x){
            poz = m;
            dr = m - 1;
        }
        else
            st = m + 1;
    }
    return poz;
}

int main(){
    fin >> n;

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

    fin >> m;

    for(;m--;){
        int t, x;
        fin >> t >> x;
        if(t == 0)
            fout << q1(x) << '\n';
        else if(t == 1)
            fout << q2(x) << '\n';
        else
            fout << q3(x) << '\n';
    }
}