#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) {
        mid = (fin + start) / 2;
        if(v[mid] <= x) {
            start = mid + 1;
        } else {
            fin = mid - 1;
        }
    }
    mid = (fin + start) / 2;
    if(v[mid] > x) {
        mid--;
    }
    if(v[mid] == x) {
        return m;
    } else {
        return -1;
    }
}

int mic(int x) {

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

int mare(int x) {

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

}

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));;
        }
    }
}