#include<fstream>
#include<iostream>
using namespace std;
int n, m, v[100002], pos;
int cautbin0(int st, int dr, int nr) ///1 3 3 3 5
{
    long long int mid=(st+dr)/2;
    if(dr-st==1)
    {
        if((v[st]!=nr) && (v[dr]!=nr))
            pos=-1; //daca nu gasim elementu' afisam -1
        return 0;
    }

    if(nr>=v[mid])
    {
        pos=mid;
        cautbin0(mid, dr, nr);
    }
    else
    {
        pos=st;
        cautbin0(st, mid, nr);
    }
}
int cautbin1(int st, int dr, int nr)
{
    long long int mid=(st+dr)/2;
    if(dr-st==1)
        return 0;
    if(nr>=v[mid])
    {
        pos=mid;
        cautbin1(mid, dr, nr);
    }
    else
    {
        pos=st;
        cautbin1(st, mid, nr);
    }
}
int cautbin2(int st, int dr, int nr)    ///1 3 3 3 5, 3
{
    long long int mid=(st+dr)/2;
    if(dr-st==1)
        return 0;
    if(nr<=v[mid])
    {
        pos=mid;
        cautbin2(st, mid, nr);
    }
    else
    {
        pos=dr;
        cautbin2(mid, dr, nr);
    }
}
int main ()
{
    int c, nr, i;
    ifstream in ("cautbin.in");
    ofstream out ("cautbin.out");
    in>>n;
    for(i=1;i<=n;i++)
        in>>v[i];
    in>>m;
    for(i=0;i<m;i++)
    {
        in>>c>>nr;
        if(!c)
        {
            cautbin0(1,n,nr);
            out<<pos<<" ";
        }
        else if(c==1)
        {
            cautbin1(1,n,nr);
            out<<pos<<" ";
        }
        else
        {
            cautbin2(1,n,nr);
            out<<pos<<" ";
        }
    }
}