#include <iostream>
#include <fstream>
using namespace std;

ifstream in("cautbin.in");
ofstream out("cautbin.out");
const int N=100000;
int a[N];

int cautare_bin0 (int p, int u, int val) {
    int mj;
    while(p<=u)
    {
        mj= p+(u-p)/2;
        if(a[mj]<=val)
            p=mj+1;
        else
            u=mj-1;
    }
    mj= p+(u-p)/2;
    if(a[mj]>val)
        mj--;
    if(a[mj]==val)
        return mj;
    return -1;
}

int cautare_bin1 (int p, int u, int val) {
    int mj;
    while(p<u){
        mj=p+(u-p)/2;
        if(a[mj]<=val)
            p=mj+1;
        else
            u=mj;
    }
    mj= p+(u-p)/2;
    if(a[mj]>val)
       --mj;
    return mj;
}

int cautare_bin2 (int p, int u, int val) {
    int mj;
    while(p<u) {
        mj=p+(u-p)/2;
        if(a[mj]<val)
            p=mj+1;
        else
            u=mj;
    }
    mj= p+(u-p)/2;
    if (a[mj] < val)
       ++ mj;
    return mj;
}

int main()
{   int i,n,m,x,y;
    in>>n;
    for(i=1;i<=n;i++)
        in>>a[i];
    in>>m;
    for(i=0;i<m;i++)
    {
        in>>x>>y;
        if(x==0)
            out<<cautare_bin0(1,n,y)<<endl;
            else if(x==1)
                out<<cautare_bin1(1,n,y)<<endl;
                else out<<cautare_bin2(1,n,y);
    }
    return 0;
}