#include <fstream>
#define Nmax 100002
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int a[Nmax],n,m;
int cautarebinara(int a[Nmax],int s,int d,int x)
{
    if(s<d)
    {
        int m=s+(d-s)/2;
        if(x==a[m])return m;
        if(x<a[m])return cautarebinara(a,s,m-1,x);
        if(x>a[m])return cautarebinara(a,m+1,d,x);
    }
    else return s;
}
void Read(int a[Nmax],int &n)
{
    int i;
    fin>>n;
    for(i=1;i<=n;i++)
    fin>>a[i];
}
int main()
{
    int i,cod,val,raspuns;
    Read(a,n);
    fin>>m;
    for(i=1;i<=m;i++)
    {
        fin>>cod>>val;
        raspuns=cautarebinara(a,1,n,val);
        if(cod==0)
        {
            if(a[raspuns]==val){
                                 while(raspuns<n&&a[raspuns+1]==val)++raspuns;
                                 fout<<raspuns<<"\n";
                               }
            else fout<<"-1\n";

        }
        else if(cod==1)
        {
            if(a[raspuns]>val)raspuns--;
            while(raspuns<n&&a[raspuns+1]<=val)++raspuns;
            fout<<raspuns<<"\n";
        }
        else
        {
            if(a[raspuns]<val) raspuns++;
            while(raspuns>1&&a[raspuns-1]>=val)--raspuns;
            fout<<raspuns<<"\n";
        }
    }
    return 0;
}