#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)
    {
        //cea mai mare pozitie pe care se afla un element cu valoarea x
        //sau -1 daca aceasta valoare nu se gaseste in sir
        int pas=pmax,i;
        for(i=0; pas ; pas>>=1)
            {
                if(i+pas<=N && v[i+pas]<=x)i+=pas;
                if(v[i]==x && v[i+1]==x)++i,pas<<=1;
            }
        if(i)g<<i<<'\n';
            else g<<-1<<'\n';
        return;

    }
    if(tip==1)
    {
        //cea mai mare pozitie pe care se afla un element cu valoarea mai mica
        //sau egala cu x in sir.
        int pas=pmax,i;
        for(i=0; pas ; pas>>=1)
            {
                if(i+pas<=N && v[i+pas]<=x)i+=pas;
                if(v[i]<=x && v[i+1]<=x)++i,pas<<=1;
            }
        if(i)g<<i<<'\n';
            else g<<-1<<'\n';
        return;
    }
    if(tip==2)
    {
        //cea mai mica pozitie pe care se afla un element cu valoarea mai mare
        //sau egala cu x in sir.
        int pas=pmax,i;
        for(i=0; pas ; pas>>=1)
            {
                if(i+pas<=N && v[i+pas]>=x)i+=pas;
                if(i>1 && v[i]>=x && v[i-1]>=x)--i;//,pas<<=1;
            }
        if(i)g<<i<<'\n';
            else g<<-1<<'\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;
}