#include <bits/stdc++.h>

using namespace std;

ifstream f("cautbin.in");
ofstream g("cautbin.out");

int solve0(int x, int v[], int s, int d){
    int m;

    while(s <= d){
        m = s + (d - s)/2;
        if(v[m] <= x)
            s = m + 1;
        else
            d = m - 1;
    }
    m = s + (d - s)/2;
    if(v[m] > x)
        m--;

    if(v[m] == x)
        return m;

    return -1;
}

int solve1(int x, int v[], int s, int d){
    int m;

    while(s < d){
        m = s + (d - s)/2;
        if(v[m] <= x)
            s = m + 1;
        else
            d = m;
    }
    m = s + (d - s)/2;
    if(v[m] > x){
        m--;
    }

    return m;
}

int solve2(int x, int v[], int s, int d){
    int m;

    while(s < d){

        m = s + (d - s)/2;
        if(v[m] < x)
            s = m + 1;
        else
            d = m;
    }
    m = s + (d - s)/2;
    if(v[m] < x){
        m++;
    }

    return m;
}

int main(){
    int n, m, tip, x;
    f >> n;

    int v[n];
    for(int i = 1; i <= n; i++){
        f >> v[i];
    }

    f >> m;
    while(m--){
        f >> tip >> x;
        if(tip == 0){
            cout << solve0(x, v, 1, n);
        }else if(tip == 1){
            cout << solve1(x, v, 1, n);
        }else{
            cout << solve2(x, v, 1, n);
        }

        if(!m){
            break;
        }
        cout << "\n";
    }
}