#include <iostream>
#include <fstream>
using namespace std;

int cautare0(int n, int t[], int x)
{
    int st = 1;
    int dr = n;

    while (st < dr) {
        int mij = (st + dr + 1) / 2;

        if (t[mij] == x) {
            st = mij;
        }
        else if (t[mij] > x) {
            dr = mij-1;
        }
        else { // t[mij] < x
            st = mij+1;
        }
    }

    if (st == dr && t[st] == x)
        return st;
    else
        return -1;
}

int cautare1(int n, int t[], int x)
{
    int st = 1;
    int dr = n;

    while (st < dr) {
        int mij = (st + dr + 1) / 2;

        if (t[mij] <= x) {
            st = mij;
        }
        else if (t[mij] > x) {
            dr = mij-1;
        }
    }

    // st == dr
    return st;
}

int cautare2(int n, int t[], int x)
{
    int st = 1;
    int dr = n;

    while (st < dr) {
        int mij = (st + dr) / 2;

        if (t[mij] < x) {
            st = mij+1;
        }
        else if (t[mij] >= x) {
            dr = mij;
        }
    }

    // st == dr
    return st;
}


int main()
{
    ifstream fin("cautbin.in");
    ofstream fout("cautbin.out");

    int n;
    int t[100001];

    fin >> n;
    for (int i = 1; i <= n; i++)
        fin >> t[i];

    int m;
    fin >> m;

    for (int i = 1; i <= m; i++) {
        int tip, x;
        fin >> tip >> x;

        if (tip == 0) {
            fout << cautare0(n, t, x) << endl;
        }
        else if (tip == 1) {
            fout << cautare1(n, t, x) << endl;
        }
        else {
            fout << cautare2(n, t, x) << endl;
        }
    }

    return 0;
}