#include <bits/stdc++.h>

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

int n, t, tip, nr;
int x[100001];

int bs0(int st, int dr, int nr)
{
    int m;
    while(st<=dr)
    {
        m=(st+dr)/2;
        if(x[m]<=nr) st=m+1;
        else dr=m-1;
    }
    m=(st+dr)/2;
    if(x[m]>nr) --m;
    if(x[m]==nr) return m;
    return -1;
}

int bs1(int st, int dr, int nr)
{
    int m;
    while(st<dr)
    {
        m=(st+dr)/2;
        if(x[m]<=nr) st=m+1;
        else dr=m;
    }
    m=(st+dr)/2;
    if(x[m]>nr) --m;
    return m;
}

int bs2(int st, int dr, int nr)
{
    int m;
    while(st<dr)
    {
        m=(st+dr)/2;
        if(x[m]<nr) st=m+1;
        else dr=m;
    }
    m=(st+dr)/2;
    if(x[m]<nr) ++m;
    return m;
}

int main()
{
    fin>>n;
    for(int i=1; i<=n; ++i) fin>>x[i];
    fin>>t;
    for(int q=1; q<=t; ++q)
    {
        fin>>tip>>nr;
        if(tip==0) fout<<bs0(1, n, nr)<<"\n";
        if(tip==1) fout<<bs1(1, n, nr)<<"\n";
        if(tip==2) fout<<bs2(1, n, nr)<<"\n";
    }
    return 0;
}