#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;

ifstream f("cautbin.in");
ofstream g("cautbin.out");

int n,t;
vector <int>v(100000);

void cautare_binara(int tip,int nr)
{
    int L=0,R=n-1,gasit=false,poz;
    if(tip==2)poz=100001;
    else poz=0;
    int m;
    while(L<=R)
    {
        m=(L+R)/2;
        switch(tip)
        {
        case 0:
                {
                    if(v[m]==nr)
                    {gasit=true;
                        if(m+1>poz)
                            poz=m+1;
                    }
                    if(v[m]<=nr)
                    {
                        L=m+1;
                    }
                    else
                    {
                        R=m-1;
                    }
                }
                break;
        case 1:
               {
                    if(v[m]<=nr)
                    {
                        gasit=true;
                        if(m+1>poz)
                            poz=m+1;
                        L=m+1;
                    }
                    else
                    {
                        R=m-1;
                    }
                }
                break;
        case 2:
                {
                    if(v[m]>=nr)
                    {
                        gasit=true;
                        if(m+1<poz)
                            poz=m+1;
                        R=m-1;
                    }
                    else
                    {
                        L=m+1;
                    }
                }

        }
    }
    if(gasit==true)
        g<<poz<<"\n";
    else
        g<<-1<<"\n";
}


int main()
{
    f>>n;
    for(int i=0;i<n;i++)
    {
        f>>v[i];
    }
    f>>t;
    int tip;
    int nr;
    for(int i=0;i<t;i++)
    {
        f>>tip>>nr;
        cautare_binara(tip,nr);
    }
    f.close();
    g.close();
}