#include <iostream>
#include <fstream>
using namespace std;
ifstream in("cautbin.in");
ofstream out("cautbin.out");
int n,m,v[100010],t,x;
int caut_bin1(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 caut_bin2(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 caut_bin3(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()
{
    in>>n;
    for(int i=1;i<=n;i++)
        in>>v[i];
    in>>m;
    while(m)
    {
    in>>t>>x;
    if(t==0)out<<caut_bin1(1,n,x)<<'\n';
    if(t==1)out<<caut_bin2(1,n,x)<<'\n';
    if(t==2)out<<caut_bin3(1,n,x)<<'\n';
    m--;
    }
    in.close();
    out.close();
    return 0;
}