#include <iostream>
#include <fstream>
#define N 100010
using namespace std;

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

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

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

int main()
{   int i,n,m,x,y;
    in>>n;
    for(i=1;i<=n;i++)
        in>>a[i];
    in>>m;
    while(m--)
    {
        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 if(x==2)
            out<<cautare_bin2(1,n,y)<<endl;
    }
    return 0;
}