#include <iostream>
#include <fstream>

using namespace std;

ifstream fin ("cautbin.in");
ofstream fout ("cautbin.out");

int cautbin0 (int v[100001], int s, int f, int x, int p)
{
    if (s<=f){
        int m=(s+f)/2;
        if (x==v[m]) p=m;
        if (x<v[m]) return cautbin0(v, s, m-1, x, p);
        else return cautbin0(v, m+1, f, x, p);
    }
    return p;
}

int cautbin1 (int v[100001], int s, int f, int x, int p)
{
    if (s<=f){
        int m=(s+f)/2;
        if (x==v[m]) p=m;
        if (x<v[m]) return cautbin1(v, s, m-1, x, p);
        else return cautbin1(v, m+1, f, x, p);
    }
    if (p!=-1) return p;
    else return f;
}

int cautbin2 (int v[100001], int s, int f, int x, int p)
{
    if (s<=f){
        int m=(s+f)/2;
        if (x==v[m]) p=m;
        if (x>v[m]) return cautbin2(v, m+1, f, x, p);
        else return cautbin2(v, s, m-1, x, p);
    }
    if (p!=-1) return p;
    else return s;
}

int main()
{
    int n, v[100001], x, s=1, f, q, nrq;
    fin >> n;
    f=n;

    for (int i=1; i<=n; ++i) {
        fin >> v[i];
    }

    fin >> nrq;

    for (int i=1; i<=nrq; ++i) {
        fin >> q >> x;
        if (q==0) fout << cautbin0(v, s, f, x, -1) << '\n';
        if (q==1) fout << cautbin1(v, s, f, x, -1) << '\n';
        if (q==2) fout << cautbin2(v, s, f, x, -1) << '\n';
    }

    return 0;
}