#include <bits/stdc++.h>

using namespace std;
ifstream in("cautbin.in");
ofstream out("cautbin.out");
int v[100000],N;
int cbin(int val)
{
    int pos=0;
    for(int msk=1<<20; msk>0; msk/=2)
        if(pos+msk<=N && v[pos+msk]<=val)
            pos+=msk;
    if(v[pos]==val)
        return pos;
    else
        return -1;
}
int cbin2(int val2)
{
    int pos2=0;
    for(int msk2=1<<20; msk2>0; msk2/=2)
        if(pos2+msk2<=N && v[pos2+msk2]<=val2)
            pos2+=msk2;
    if(v[pos2]<=val2)
        return pos2;
}
int cbin3(int val3)
{
    int pos3=0;
    for(int msk3=1<<20; msk3>0; msk3/=2)
    {
        if(pos3+msk3<=N && v[pos3+msk3]<val3)
            pos3+=msk3;
        if(v[pos3++]>=val3)
            return pos3-1;
    }
}
int main()
{
    int i,M,C,x;
    in>>N;
    for(i=1; i<=N; i++)
        in>>v[i];
    in>>M;
    for(i=1; i<=M; i++)
    {
        in>>C>>x;
        if(C==0)
            out<<cbin(x)<<'\n';
        else if(C==1)
            out<<cbin2(x)<<'\n';
        else if(C==2)
            out<<cbin3(x)<<'\n';
    }
    return 0;
}