#include<fstream>
#include<iostream>
using namespace std;

int v[1000000],n,m,i,k;

int cautare0(int li,int ls,int x)
{
    while(li<=ls)
    {
        m=(li+ls)/2;
        if(v[m]<=x) li=m+1;
        else ls=m-1;
    }
    m=(li+ls)/2;
    if(v[m]>x) m--;
    if(v[m]==x) return m;
    else return -1;
}

int cautare1(int li,int ls,int x)
{
    while(li<ls)
    {
        m=(li+ls)/2;
        if(v[m]<=x) li=m+1;
        else ls=m;
    }
    m=(li+ls)/2;
    if(v[m]>x) m--;
    return m;
}

int cautare2(int li,int ls,int x)
{
    while(li<ls)
    {
        m=(li+ls)/2;
        if(v[m]<x) li=m+1;
        else ls=m;
    }
    m=(li+ls)/2;
    if(v[m]<x) m++;
    return m;
}

int main()
{int x; int mi;
    ifstream f("cautbin.in");
    ofstream g("cautbin.out");
    f>>n;
    for(i=1;i<=n;i++)
        f>>v[i];
        f>>mi;
    for(i=1;i<=mi;i++)
    {
        f>>k>>x;
        if(k==0) g<<cautare0(1,n,x)<<'\n';
        else if(k==1) g<<cautare1(1,n,x)<<'\n';
        else if(k==2) g<<cautare2(1,n,x)<<'\n';
    }
}