#include <bits/stdc++.h>
#define N 100001
using namespace std;
int v[N];
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int Caut1 (int st, int dr, int x) {

    int mij;
    while (st <= dr) {
        mij = (st + dr) / 2;
        if (v[mij] <= x)
            st = mij + 1;
        else
            dr = mij - 1;
    }
    mij = (st + dr) / 2;

    if (v[mij] > x) mij --;
    if (v[mij] == x)
        return mij;
    return -1;
}

int Caut2 (int st, int dr, int x) {

    int mij, drc = dr ;
    while (st < dr){
        mij = (st + dr) / 2;
        if (v[mij] <= x)
            st = mij + 1;
        else
            dr = mij;
    }

    mij = (st + dr) / 2;
    if (v[mij] > x)
       -- mij;
    return mij;
}

int Caut3 (int st, int dr, int x) {

    int mij;
    while (st < dr) {
        mij = (st + dr) / 2;
        if (v[mij] < x)
            st = mij + 1;
        else
            dr = mij;
    }

    mij = (st + dr) / 2;
    if (v[mij] < x)
       ++ mij;
    return mij;
}

int main () {
    int n, m, tip, val;

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

    fin>>m;
    while(m)
    {
        fin>>tip>>val;
        if (tip == 0)
            fout<<Caut1(1,n,val)<<"\n";
        if (tip == 1)
            fout<<Caut2(1,n,val)<<"\n";
        if (tip == 2)
            fout<<Caut3(1,n,val)<<"\n";
        m--;
    }
}