#include <fstream>
using namespace std;
ifstream fin ("cautbin.in");
ofstream fout("cautbin.out");
int n,k,p,v[100002],x;
void caut1 (int s,int d)
{
    if (s<=d)
    {
        int m=(s+d)/2;
        if (x==v[m])
            p=m;
        if (x<v[m])
            caut1 (s,m-1);
        else
            caut1 (m+1,d);
    }
}
void caut2 (int s,int d)
{
    if (s<=d)
    {
        int m=(s+d)/2;
        if (x>=v[m])
            p=m;
        if (x<v[m])
            caut2 (s,m-1);
        else
            caut2 (m+1,d);
    }
}
void caut3 (int s,int d)
{
    if (s<=d)
    {
        int m=(s+d)/2;
        if (x<=v[m])
            p=m;
        if (x<=v[m])
            caut3 (s,m-1);
        else
            caut3 (m+1,d);
    }
}
int main()
{
    fin>>n;
    for (int i=1;i<=n;i++)
        fin>>v[i];
    fin>>k;
    for (int i=1;i<=k;i++)
    {
        int y;
        fin>>y>>x;
        p=-1;
        if (y==0)
            caut1(1,n);
        if (y==1)
            caut2 (1,n);
        if (y==2)
            caut3 (1,n);
        fout<<p<<"\n";
    }
    return 0;
}