#include <fstream>

using namespace std;

const int NMAX =100000;

int v[NMAX+5];

int n, nr, cerinta, param, i;

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

int subtask1(int st, int dr, int a)
{
    int med;
    while (st < dr) {
        med = (st + dr) / 2;
        if (v[med] <= a)
            st = med+ 1;
        else
            dr = med - 1;
    }
    med = (st + dr) / 2;

    if (v[med] > a)
        med --;
    if (v[med] == a)
        return med;
    return -1;
}

int subtask2(int st, int dr, int a)
{
    int med;
    while (st < dr)
    {
        med = (st + dr) / 2;
        if (v[med] <= a)
            st = med+ 1;
        else
            dr = med - 1;
    }
    med = (st + dr) / 2;

    if (v[med] > a)
        med --;
    return med;
}

int subtask3(int st, int dr, int a)
{
    int med;
    while(st<dr)
    {
        med= (st+dr)/2;
        if(v[med]<a)
            st=med+1;
        else
            dr=med;
    }
    med = (st+dr)/2;
    if(v[med]<a)
        med++;
    return med;
}

int main()
{
    fin>>n;
    for(i=1; i<=n; i++)
    {
        fin>>v[i];
    }
    fin>>nr;
    while(nr--)
    {
        fin>>cerinta>> param;
        if(cerinta == 0)
            fout<<subtask1(1,n,param)<<"\n";
        if(cerinta == 1)
            fout<<subtask2(1,n,param)<<"\n";
        if(cerinta == 2)
            fout<<subtask3(1,n,param)<<"\n";
    }
    return 0;
}