#include <fstream>

#define vL 100001

using namespace std;

ifstream in;
ofstream out;

int v[vL];
int MAX,N;

inline int BS6161(int val)
{
    int pow=MAX,pos;

    for(pos=0;pow;pow>>=1)
        if(pos+pow<=N&&v[pos+pow]<=val) pos+=pow;

    if(v[pos]==val) return pos;
    else return -1;
}

inline int BS6061(int val)
{
    int pow=MAX,pos;

    for(pos=0;pow;pow>>=1)
        if(pos+pow<=N&&v[pos+pow]<=val) pos+=pow;

    return pos;
}

inline int BS6261(int val)
{
    int pow=MAX,pos;

    for(pos=N;pow;pow>>=1)
        if(pos-pow>0&&v[pos-pow]>=val) pos-=pow;

    return pos;
}

int main()
{
    int M;

    in.open("cautbin.in");

    in>>N;
    for(int i=1;i<=N;++i) in>>v[i];

    in>>M;

    for(MAX=1;MAX<N;MAX<<=1);

    out.open("cautbin.out");

    for(int x,y;M--;)
    {
        in>>x>>y;
        if(x==0) out<<BS6161(y)<<'\n';
        if(x==1) out<<BS6061(y)<<'\n';
        if(x==2) out<<BS6261(y)<<'\n';
    }

    in.close();
    out.close();

    return 0;
}