#include <iostream>
#include <fstream>
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");

int n,m,v[100001],i,a,b;
int cautbin0(int vmin, int vmax, int x)
{
    int vmij;
    while(vmin<=vmax)
    {
        vmij=vmin+(vmax-vmin)/2;
        if(v[vmij]<=x)
        {
            vmin=vmij+1;
        }
        else vmax=vmij-1;
    }
    vmij=vmin+(vmax-vmin)/2;
    if(v[vmij]>x) vmij--;
    if(v[vmij]==x) return vmij;
    else return -1;
}
int cautbin1(int vmin, int vmax, int x)
{
    int vmij;
    while(vmin<vmax)
    {
        vmij=vmin+(vmax-vmin)/2;
        if(v[vmij]<=x)
        {
            vmin=vmij+1;
        }
        else vmax=vmij;
    }
    vmij=vmin+(vmax-vmin)/2;
    if(v[vmij]>x) vmij--;
    return vmij;
}
int cautbin2(int vmin, int vmax, int x)
{
    int vmij;
    while(vmin<vmax)
    {
        vmij=vmin+(vmax-vmin)/2;
        if(v[vmij]<x) vmin=vmij+1;
        else vmax=vmij;
    }
    vmij=vmin+(vmax-vmin)/2;
    if(v[vmij]<x) vmij++;
    return vmij;
}
int main()
{
    f>>n;
    for(i=1;i<=n;i++)
        f>>v[i];
    f>>m;
    for(i=1;i<=m;i++)
    {
        f>>a>>b;
        if(a==0) g<<cautbin0(1,n,b)<<"\n";
        if(a==1) g<<cautbin1(1,n,b)<<"\n";
        if(a==2) g<<cautbin2(1,n,b)<<"\n";
    }
    return 0;
}