#include <iostream>
#include <fstream>

using namespace std;

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

void citireVector(int &n,int v[])
{
    f>>n;
    for(int i=1;i<=n;i++)
        f>>v[i];
}


int CautareBinara1(int st,int dr,int v[],int elem)
{
    if (st+1>=dr){
        return st;
    }
    else {
        int m=(st+dr)/2;
        if (elem<v[m])
            return CautareBinara1(st,m,v,elem);
        else
            return CautareBinara1(m,dr,v,elem);
    }
}

int verif(int elem,int n,int v[])
{
    int m = CautareBinara1(0,n+1,v,elem);
    if (v[m]==elem)
        return m;
    else return -1;
}

int CautareBinara2(int st,int dr,int v[],int elem)
{
    if (st+1>=dr){
        return dr;
    }
    else {
        int m=(st+dr)/2;
        if (elem<=v[m])
            return CautareBinara2(st,m,v,elem);
        else
            return CautareBinara2(m,dr,v,elem);
    }
}

void rezolvare(int n,int v[])
{
    int intrebari,tip,elem;
    f>>intrebari;
    for(int i=1;i<=intrebari;i++)
    {
        f>>tip>>elem;
        if (tip==0)
            g<<verif(elem,n,v);
        if(tip==1)
            g<<CautareBinara1(0,n+1,v,elem);
        if(tip==2)
            g<<CautareBinara2(0,n+1,v,elem);
        g<<'\n';
    }
}



int main()
{
    int n,v[100001];
    citireVector(n,v);
    rezolvare(n,v);
    return 0;
}