#include <fstream>
#include <iostream>
#include <vector>
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
vector <unsigned int> v;
int n;
int cautbin(int k) {
    int i = 0, j = n;
    while (i!=j) {
        int mid = (i + j)/2;
        if(v[mid] > k) {
            i = mid;
        } else if (v[mid] < k) {
            j = mid;
        } else {
            return mid;
        }
    }
    if (i == j && v[i] != k) {
        return -1;
    }
}
int main()
{
    int x, m, op;
    fin>>n;
    v.push_back(0);
    for(int i = 1 ; i <= n; i++) {
        fin>>x;
        v.push_back(x);
    }
    v.push_back(0);
    fin>>m;
    for(int i = 1; i <=m; i++) {
        fin>>op>>x;
        int o = cautbin(x);
        bool aux = false;
        if (op == 0) {
            while(v[o] == v[o + 1]) {
                o++;
            }
            fout<<o<<'\n';
        } else if (op == 2) {
            while(v[o] == v[o - 1]) {
                o--;
                aux = true;
            }
            if(!aux && v[o]!=x)
            o--;
            fout<<o<<'\n';

        } else {
            while(v[o] == v[o + 1]) {
                o++;
                aux = true;
            }
            if(!aux && v[o]!=x)
            o++;
            fout<<o<<'\n';
        }
    }
    fin.close();
    fout.close();
    return 0;
}