#include <fstream>
#define Nmax 100099
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");

int N,M,pmax,v[Nmax];

inline void ReadInput()
{
    f>>N;
    for(int i=1;i<=N;++i)f>>v[i];
    f>>M;
}

void Querry()
{
    int tip,x;
    f>>tip>>x;
    if(!tip)
    {
        int pas=pmax,i;
        for(i=0; pas ; pas>>=1)
            {
                if(i+pas<=N && v[i+pas]<=x)i+=pas;

            }
        if (v[i]!=x) g<<-1<<'\n';
            else g<<i<<'\n';
        return;

    }
    if(tip==1)
    {
        int pas=pmax,i;
        for(i=0; pas ; pas>>=1)
            {
                if(i+pas<=N && v[i+pas]<=x)i+=pas;

            }
        g<<i<<'\n';
        return;
    }
    if(tip==2)
    {
        int pas=pmax,i;
        for(i=N; pas ; pas>>=1)
            {
                if(i-pas>0 && v[i-pas]>=x)i-=pas;

            }
        g<<i<<'\n';
        return;
    }
}

int main()
{
    ReadInput();
    for(pmax=1;pmax<N;pmax<<=1);
    for(int i=1;i<=M;++i)Querry();
    f.close();g.close();
    return 0;
}