#include<bits/stdc++.h>
#define in f
#define out g
using namespace std;

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


int n;
int v[100010];
int m;
int code;
int x;

int bin(int x) {

    int start = 1;
    int fin = n;
    int mid;
    while(start <= fin) {
        if(fin == start) {
            return -1;
        }
        mid = (fin - start) / 2 + start;
        if((v[mid + 1] != x)&&(v[mid] == x)) {
            return mid;
        } else {
            if(v[mid] <= x) {
                start = mid + 1;;
            } else {
                if(v[mid] > x) {
                    fin = mid;
                }
            }
        }
    }

}

int mic(int x) {

    int start = 1;
    int fin = n;
    int mid;
    while(start < fin) {
        mid = start + (fin - start) / 2;
        if((v[mid] <= x)&&(v[mid + 1] > x)) {
            return mid;
        }
        if(v[mid] <= x) {
            start = mid + 1;
        } else {
            if(v[mid] > x){
                fin = mid;
            }
        }
    }
}

int mare(int x) {


    int start = 1;
    int fin = n;
    int mid;
    while(start < fin) {
        mid = start + (fin - start) / 2;
        if((v[mid] >= x)&&(v[mid - 1] < v[mid])) {
            return mid;
        }
        if(v[mid] >= x) {
            fin = mid;
        } else {
            if(v[mid] < x){
                start = mid + 1;
            }
        }
    }

}

int main() {

    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &v[i]);
    }
    scanf("%d", &m);
    for(int i = 1; i <= m; i++) {
        scanf("%d%d", &code, &x);
        if(code == 0) {
             printf("%d\n", bin(x));
        }
        if(code == 1) {
            printf("%d\n", mic(x));
        }
        if(code == 2) {
            printf("%d\n", mare(x));;
        }
    }
}