#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 pos = 0;
    int step = 1;
    for(step = 1; step < n; step *= 2);

    for(int i = 1; step > 0; step /= 2) {
        if(step + pos <= n && v[pos + step] <= x)
            pos += step;
    }
    if(v[pos] == x)
        out << pos << "\n" ;
    else
        out << "-1" << "\n";
}

int bin1(int x) {

    int pos = 0;
    int step = 1;
    for(step = 1; step < n; step *= 2);

    for(int i = 1; step > 0; step /= 2) {
        if(step + pos <= n && v[pos + step] <= x)
            pos += step;
    }
    out << pos << "\n";
}

int bin2(int x) {

    int pos = n;
    int step = 1;
    for(step = 1; step < n; step *= 2);

    for(int i = 1; step > 0; step /= 2) {
        if(pos - step > 0 && v[pos - step] >= x)
            pos -= step;
    }
    out << pos << "\n";
}


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) {
            bin(x);
        }
        if(code == 1) {
            bin1(x);
        }
        if(code == 2) {
            bin2(x);
        }
    }
}