#include<fstream>
using namespace std;

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

#define MAX 100010

int v[MAX],N,Right;
int max (int a, int b)
{
    if (a>b)
        return a;
    return b;
}
void cautare_binara(int x,int op)
{
    int mid,pos=-1,Left=1,Right=N;
    if(op==0)
    {
        while(Left<=Right)
        {
            mid=(Left+Right)/2;
            if(v[mid]==x)
                pos=max(pos,mid);
            if(x>=v[mid])
            {
                Left=mid+1;
            }
            else
                Right=mid-1;

        }
        out<<pos<<'\n';
    }
    else if(op==1)
    {
      while(Left<=Right)
        {
            mid=(Left+Right)/2;
            if(v[mid]<=x)
                pos=max(pos,mid);
            if(x>=v[mid])
            {
                Left=mid+1;
            }
            else
                Right=mid-1;

        }
        out<<pos<<'\n';
    }
    else if(op==2)
    {
        pos=N;
         while(Left<=Right)
        {
            mid=(Left+Right)/2;
            if(v[mid]>=x)
                pos=min(pos,mid);
            if(x<=v[mid])
            {
                Right=mid-1;
            }
            else
                Left=mid+1;

        }
        out<<pos<<'\n';
    }

}

int main()
{

    in>>N;
    int i;
    for(i=1;i<=N;i++)
        in>>v[i];
    in>>Right;
    int p,v;
    for(int i=1;i<=Right;i++)
    {
        in>>p>>v;

        cautare_binara(v,p);
    }
    return 0;
}