#include <iostream>
#include <fstream>
#include <cmath>
#include <cstdlib>
//#include <conio.h>
#include <windows.h>
using namespace std;

int f1(int v[], int x, int s, int d) {
    int mij = s + (d - s) >> 1;
    if (s == d) {
        return (v[mij] == x ? mij : -1);
    }

    if (x < v[mij]) {
         return (f1(v, x, s, mij - 1));
    } else
    {
        if (v[d] == x) return d;
        else return (f1(v, x, mij, d-1));
    }
}

int f2(int v[], int x, int s, int d) {
    int m;
    while (s < d) {
        m = s + (d - s) >> 1;
        if (x < v[m]) {
            d = m - 1;
        } else {
            s = m;
            if (x == v[d])
                return d;
            else
                d = d - 1;
        }
    }
    return s;
}

// cel mai din stanga numar mai mare ca x
int f3(int v[], int x, int s, int d) {
    int m;
    while (s < d) {
        Sleep(200);
        if (x > v[m]) { // daca v[m] nu e numarul cautat
            s = m + 1; // cauta in numerele mai mari ca v[m]
        } else { // daca e posibil ca v[m] sa fie numarul cautat
            d = m;
            if (x == v[s])
                return s;
            else
                s = s + 1;
        }
    }
    return s;
}

int factorial (int n) {
    if (n == 1) return 1;
    else return ( n * factorial (n - 1));
}

int main() {
    ifstream input("cautbin.in");
    ofstream output("cautbin.out");
    int n;
    int m;
    int i;
    int c, x;
    int *v;
    input >> n;
    v = (int*) malloc ((n + 1) * sizeof(int));
    for (i = 1; i <= n; i++)
        input >> v[i];
    input >> m;
    while (m > 0) {
        input >> c >> x;
        switch (c) {
            case 0:
                output << f1(v, x, 1, n) << "\n";
                break;
            case 1:
                output << f2(v, x, 1, n) << "\n";
                break;
            case 2:
                output << f3(v, x, 1, n) << "\n";
                break;
            default:
                break;
        }
        m--;
    }
    input.close();
    output.close();
    return(0);
}