#include <bits/stdc++.h>

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

int a[100005],n,m;

void CautBin0(int x)
{
    int mij,st,dr,poz;
    if(x<a[1])
    {
        fout<<"-1\n";
        return;
    }
    if(x>a[n])
    {
        fout<<"-1\n";
        return;
    }
    st=1;dr=n;
    poz=-1;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(a[mij]==x)
        {
            poz=mij;
            st=mij+1;
        }
        else if(a[mij]<x)
            st=mij+1;
        else dr=mij-1;
    }
    fout<<poz<<"\n";
}

void CautBin1(int x)
{
    int mij,st,dr,poz;
    st=1;dr=n;
    poz=-1;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(a[mij]<=x)
        {
            st=mij+1;
            poz=mij;
        }
        else dr=mij-1;
    }
    fout<<poz<<"\n";
}
void CautBin2(int x)
{
    int mij,st,dr,poz;
    st=1;dr=n;
    poz=-1;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(a[mij]>=x)
        {
            dr=mij-1;
            poz=mij;
        }
        else st=mij+1;
    }
    fout<<poz<<"\n";
}

void Citire()
{
    int i,x,y;
    fin>>n;
    for(i=1;i<=n;i++)
        fin>>a[i];
    fin>>m;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y;
        if(x==0) CautBin0(y);
        else if(x==1) CautBin1(y);
        else CautBin2(y);
    }
    fin.close();
    fout.close();
}

int main()
{
    Citire();
    return 0;
}