#include <bits/stdc++.h>
//#include <fstream>
using namespace std;
int cautbin(long long x, long long v[], int s, int d, int &poz) {
    if(s > d) {
        poz = d;
        return -1;
    }
    else {
        int mij;
        if(s % 2 == 1 && d % 2 == 1)
            mij = s/2 + d/2 + 1;
        else mij = s/2 + d/2;
        if(v[mij] < x)
            return cautbin(x, v, mij + 1, d, poz);
        else
            if(v[mij] > x)
                return cautbin(x, v, s, mij - 1, poz);
            else
                return mij;
    }
}
int main()
{
    ifstream f("cautbin.in");
    ofstream g("cautbin.out");
    int n, m, i, inst, y, poz = 0;
    long long x, v[100001];
    f>>n;
    for(i=0; i<n; i++)
        f>>v[i];
    f>>m;
    while(m != 0) {
        f>>inst;
        f>>x;
        if(inst == 0) {
            y = cautbin(x, v, 0, n-1, poz);
            if(y == -1)
                g<<-1<<endl;
            else {
                while(v[y + 1] == x) {
                    y = cautbin(x, v, y + 1, n-1, poz);
                }
                g<<y+1<<endl;
            }
        } else if(inst == 1) {
            y = cautbin(x, v, 0, n-1, poz);
            if(y == -1)
                g<<poz + 1<<endl;
            else {
                while(v[y + 1] == x) {
                    y = cautbin(x, v, y + 1, n-1, poz);
                }
                g<<y+1<<endl;
            }
        } else if(inst == 2) {
            y = cautbin(x, v, 0, n-1, poz);
            if(y == -1)
                g<<poz + 2;
            else {
                while(v[y - 1] == x) {
                    y = cautbin(x, v, 0, y - 1, poz);
                }
                g<<y+1<<endl;
            }
        }else m++;
        m--;
    }


    return 0;
}