#include <fstream>

using namespace std;

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

int n, m, v[100005];

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

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

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

int main()
{
    int i, nr, x;
    fin >> n;
    for(i = 1; i <= n; i++)
        fin >> v[i];
    fin >> m;
    for(i = 1; i <= m; i++)
    {
        fin >> nr >> x;
        if(nr == 0)
            fout << CautBin0(x) << "\n";
        else if(nr == 1)
            fout << CautBin1(x) << "\n";
        else
            fout << CautBin2(x) << "\n";
    }
    return 0;
}