#include <fstream>
using namespace std;
ifstream cin("cautbin.in");
ofstream cout("cautbin.out");
int cautbin (int x,int n,int a[])
{
    int ls = 1,ld=n;
    int m, pozitie = 0;
    while (ls <=ld)
    {
        m = ls + (ld-ls)/2;
        if (a[m] <=x) {ls=m+1;pozitie = m;}
        else ld = m-1;
    }
    return pozitie;
}
int cautbin1 (int x, int n, int a[])
{
    int tmp = cautbin(x, n, a);
    if(a[tmp] == x) return tmp;
    return -1;
}
int cautbin2 (int x,int n,int a[])
{
    return cautbin(x,n,a);
}
int cautbin3 (int x,int n,int a[])
{
    return cautbin(x-1,n,a)+1;
}
int main()
{

    int n,x;
    cin>>n;
    int a[100005];
    for (int i=1; i<=n; i++) cin >> a[i];
    int intr,tip;
    cin >> intr;
    while (intr-- >0)
    {
        cin >> tip >> x;
        if (tip == 0) cout << cautbin1(x,n,a) << '\n';
        else if (tip == 1) cout << cautbin2(x,n,a) << '\n';
        else if (tip == 2) cout << cautbin3(x,n,a) << '\n';

    }
    return 0;
}