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


}

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

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

}

int main() {

    in >> n;
    for(int i = 1; i <= n; i++) {
        in >> v[i];
    }
    in >> m;
    for(int i = 1; i <= m; i++) {
        in >> code;
        in >> x;
        if(code == 0) {
            out << bin(x) << endl;
        }
        if(code == 1) {
            out << mic(x) << endl;
        }
        if(code == 2) {
            out << mare(x) << endl;
        }
    }
}