#include <fstream>

using namespace std;
int a[1000000];
ifstream in ("cautbin.in");
ofstream out ("cautbin.out");
int intrebare0(int nr, int a[100000],int n)
{
    int ok=0,m=n,max=n;
    while(a[m]!=nr || m>max)
    {
        if(a[m]!=nr)
        m=m/2;
        else return m;
        if(a[m]>nr) m=m/2;
        else m=m+m/2;
        if(a[m]==nr)
        {
            max=m;
            if(a[m+1]==nr) m=m+1;
            else return m;
        }
        if(m<1) return -1;
    }

}
int intrebare1(int nr, int a[100000],int n)
{
    int ok=0,m=n,max=n;
    while(a[m]!=nr || m>max)
    {
        if(a[m]!=nr)
        m=m/2;
        else return m;
        if(a[m]>nr) m=m/2;
        else m=m+m/2;
        if(a[m]==nr)
        {
            max=m;
            if(a[m+1]==nr) m=m+1;
            else return m;
        }
        else
        if(a[m]<nr)
        {
            max=m;
            while(m!=0)
            if(a[m+1]<nr) m=m+1;
            else return m;
        }
    }
}
int intrebare2 (int nr, int a[100000],int n)
{
    int ok=0,m=n,max=n;
    while(a[m]!=nr || m>max)
    {
        if(a[m]!=nr)
        m=m/2;
        else return m;
        if(a[m]>nr) m=m/2;
        else m=m+m/2;
        if(a[m]==nr)
        {
            max=m;
            if(a[m+1]==nr) m=m+1;
            else return m;
        }
        else
        if(a[m]<nr)
        {
            max=m;
            while(m!=0)
            if(a[m+1]<nr) m=m+1;
            else return m+1;
        }
    }
}
int main()
{   int n,m,pi;
    in >> n;
    for(int i=1;i<=n;i++)
        in >> a[i];
    in >> m;
    for(int i=1;i<=m;i++)
    {
        int intr,nr;
        in >> intr >> nr;
        if(intr==0) out << intrebare0(nr,a,n)<<endl;
        if(intr==1) out << intrebare1(nr,a,n) <<endl;
        if(intr==2) out << intrebare2(nr,a,n);
    }
    return 0;
}