#include <iostream>
#include <fstream>
using namespace std;
int v[100001];
int bsearch0 (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 bsearch1 (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 bsearch2 (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 () {
    int i,n,m,tip,val;
    ifstream f("cautbin.in");
    ofstream g("cautbin.out");
    f>>n;
    for (i =1; i<=n;i++)
        f>>v[i];f>>m;
    while (m--){
          f>>tip>>val;
          if (tip == 0) g<<bsearch0(1,n,val)<<"\n";
          if (tip == 1) g<<bsearch1(1,n,val)<<"\n";
          if (tip == 2) g<<bsearch2(1,n,val)<<"\n";}
    return 0;}