#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

#define MAX 100000

int n,s;
int a[MAX];

int caut1(int x)
{
    int st=0,dr=n,m;
    s=0;
    while(st<=dr){
        m=(st+dr)/2;
        if(a[m]==x)
            s=m;
        if(a[m]>x)
            dr=m-1;
        else
            st=m+1;
    }
    return s;
}

int caut2(int x)
{
    int st=0,dr=n,m;
    while(st<=dr){
        m=(st+dr)/2;
        if(a[m]<=x){
            s=m;
            st=m+1;
        }
        else
            dr=m-1;
    }
    return s;
}

int caut3(int x)
{
    int st=0,dr=n,m;
    while(st<=dr){
        m=(st+dr)/2;
        if(a[m]>=x){
            s=m;
            dr=m-1;
        }
        else
            st=m+1;
    }
    return s;
}

int main()
{
    fin>>n;
    int i,x,y,t;
    for(i=1;i<=n;i++)
        fin>>a[i];
    fin>>t;
    while(t--)
    {
        fin>>x>>y;
        if(x==0)
        {
            if(caut1(y))
                fout<<caut1(y)<<endl;
            else
                fout<<-1<<endl;
        }
        if(x==1)
            fout<<caut2(y)<<endl;
        if(x==2)
            fout<<caut3(y)<<endl;
    }
    fin.close();
    fout.close();
    return 0;
}