#include <iostream>
#include <fstream>
using namespace std;
int v[100010];

int b1 (int p, int n, int x) {
    int m;

    while (p <= n) {
        m = (p + n) / 2;
        if (v[m] <= x)
            p = m + 1;
        else
            n = m - 1;
    }
    m = (p + n) / 2;

    if (v[m] > x) m --;
    if (v[m] == x)
        return m;
    return -1;
}

int b2(int p, int n, int x) {
    int m;

    while (p < n){
        m = (p + n) / 2;
        if (v[m] <= x)
            p = m + 1;
        else
            n = m;
    }

    m = (p + n) / 2;
    if (v[m] > x)
       m--;
    return m;
}

int b3 (int p, int n, int x) {
    int m;

    while (p < n) {
        m = (p + n) / 2;
        if (v[m] < x)
            p = m + 1;
        else
            n = m;
    }

    m = (p + n) / 2;
    if (v[m] < x)
       m++;
    return m;
}

int main () {
    int i, n, m, k,x;
    ifstream fin("cautbin.in");
    ofstream fout("cautbin.out");
    fin>>n;
    for (i = 1; i <= n; ++ i)
        fin>>v[i];

    fin>>m;

    while (m){
          fin>>k>>x;
          if (k == 0)
             fout<<b1(1, n, x)<<"\n";
          if (k == 1)
             fout<<b2(1, n, x)<<"\n";
          if (k == 2)
             fout<<b3(1, n, x)<<"\n";
             m--;
    }
  return 0;
}