#include <bits/stdc++.h>

using namespace std;
const int NMAX = 100005;

int N, M, tip, val;
int v[NMAX];

int read(){
    scanf("%d", &N);
    for(int i=1; i<=N; i++)
         scanf("%d", &v[i]);
}

int search0(int x, int y){
    int m;

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

int search1(int x, int y){
    int m;

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

int search2(int x, int y){
    int m;

    while(x < y){
        m = (x + y) / 2;
        if(v[m] < val)
            x = m + 1;
        else
            y = m;
    }
    m = (x + y) / 2;
    if(v[m] < val)
        m++;
    return m;
}

int main(){

    freopen("cautbin.in", "r", stdin);
    freopen("cautbin.out", "w", stdout);

    read();
    scanf("%d", &M);

    for(int i=0; i<M; i++){
        scanf("%d%d", &tip, &val);
        if(tip == 0)
            printf("%d\n", search0(1, N));
        else if(tip == 1)
            printf("%d\n", search1(1, N));
        else if(tip == 2)
            printf("%d\n", search2(1, N));
    }

    return 0;
}