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

int n,m,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 left=1,right=n,middle;
        while(left<=right)
        {
            middle=(left+right)/2;
            if(v[middle]==x && v[middle+1]!=x){g<<middle<<'\n';return;}
            else if(v[middle]==x && v[middle+1]==x)left=middle+1;
            if(v[middle]>x)right=middle-1;
            else if(v[middle]<x)left=middle+1;
        }
        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 left=1,right=n,middle;
        while(left<=right)
        {
            middle=(left+right)/2;
            if(v[middle]<=x && v[middle+1]>x){g<<middle<<'\n';return;}
            else if(v[middle]<=x && v[middle+1]<=x)left=middle+1;
            if(v[middle]>x)right=middle-1;
            else if(v[middle]<x)left=middle+1;
        }
        g<<right<<'\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 left=1,right=n,middle;
        while(left<=right)
        {
            middle=(left+right)/2;
            if(v[middle]>=x && v[middle-1]<x){g<<middle<<'\n';return;}
            else if(v[middle]>=x && v[middle-1]>=x)right=middle-1;
            if(v[middle]>x)right=middle-1;
            else if(v[middle]<x)left=middle+1;
        }
        g<<left<<'\n';
        return;
    }
}

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