#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
using namespace std;
#define NMAX 100005
int a[NMAX], i, n, m, op, x;
ifstream in("cautbin.in");
ofstream out("cautbin.out");
int cb0(int start, int stop)
{
    int m;
    m = (start+stop)/2;
    while(start<=stop)
    {
        m = (start+stop)/2;
        if(a[m]<=x) start = m + 1;
                else stop = m - 1;
    }
    m = (start+stop)/2;
    if(a[m]>x) m--;
    if(a[m]==x) return m;
    else return -1;
}
int cb1(int start, int stop)
{
    int m;
    m = (start+stop)/2;
    while(start<stop)
    {
        m=(start+stop)/2;
        if(a[m]<=x) start = m+1;
        else stop = m;
    }
    m = (start+stop)/2;
    if(a[m]>x) m--;
    return m;
}
int cb2(int start, int stop)
{
    int m;
    m = (start+stop)/2;
    while(start<stop)
    {
        m=(start+stop)/2;
        if(a[m] < x) start = m+1;
        else stop = m;
    }
     m = (start+stop)/2;
    if (a[m]<x) m++;
    return m;
}
int main()
{
    in.sync_with_stdio(false);
    out.sync_with_stdio(false);
    in>>n;
    for(i=1;i<=n;i++)
        in>>a[i];
    in>>m;
    for(i=1;i<=m;i++)
    {
        in>>op>>x;
        if(op == 0)
        {
            out << cb0(1, n)<<"\n";
        }
        else if(op == 1)
        {
            out<<cb1(1,n)<<"\n";
        }
        else if(op == 2)
        {
            out<<cb2(1,n)<<"\n";
        }
    }

    return 0;
}