#include <iostream>
#include <fstream>
#include <stdlib.h>
#include <stdio.h>
using namespace std;
#define N 100010
int v[N];

int search0 (int p, int u, int key)
{
    int m;
    while (p<=u)
    {
        m=(p+u)/2;
        if (v[m]<=key)
            p=m+1;
        else 
            u=m-1;
    }
    m=(p+u)/2;
    if(v[m]> key)
        m--;
    if(v[m]==key)
        return m;
    return -1;
}

int search1 (int p, int u, int key) 
{
    int m, n=u;
    while (p<u)
    {
        m=(p+u)/2;
        if(v[m]<=key)
            p=m+1;
        else 
            u=m;
    }
    m=(p+u)/2;
    if (v[m]> key)
        m--;
    return m;
}

int search2(int p, int u, int key)
{
    int m;
    while (p<u)
    {
        m=(p+u)/2;
        if (v[m]<key)
            p=m+1;
        else 
            u=m;
    }
    m=(p+u)/2;
    if(v[m]<key)
        m++;
    return m;
}

int main ()
{
    ifstream fin("cautbin.in");
    ofstream fout("cautbin.out");
    int i, n, m, tip, val;
    fin>>n;
    for (i=1; i<=n; i++)
        fin>>v[i];
    fin>>m;
    while (m--)
    {
        fin>>tip; fin>>val;
        if (tip==0)
            fout<<search0(1, n, val)<<"\n";
        if(tip==1)
            fout<<search1(1, n, val)<<"\n";
        if(tip==2)
            fout<<search2(1, n, val)<<"\n";
    }
    return 0;
}