#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

ifstream in("cautbin.in");
ofstream out("cautbin.out");

long v[100003];
int n,k,t,a;

int bin0(int a) {
    int st = 0;
    int dr = n-1;
    int mid = 0;
    while(st <= dr) {
        mid = st + (dr-st)/2;
        if(v[mid] <= a)
            st = mid+1;
        else
            dr = mid-1;
    }
    if(v[dr] == a)
        return dr;
    else
        return -2;
}

int bin1(int a) {
    int st = 0;
    int dr = n-1;
    int mid = 0;
    while(st <= dr) {
        mid = st + (dr-st)/2;
        if(v[mid] <= a)
            st = mid+1;
        else
            dr = mid-1;
    }
    return dr;
}

int bin2(int a) {
    int st = 0;
    int dr = n-1;
    int mid = 0;
    while(st <= dr) {
        mid = st + (dr-st)/2;
        if(v[mid] >= a)
            dr = mid-1;
        else
            st = mid+1;
    }
    return st;
}

int main() {

    in >> n;

    for(int i = 0; i < n; i++)
        in >> v[i];
    in >> k;

    for(int i = 0; i < k; i++) {
        in >> t >> a;
        if(t == 0)
            out << bin0(a)+1 << '\n';
        else if(t == 1)
            out << bin1(a)+1 << '\n';
        else
            out << bin2(a)+1 << '\n';
  }

    return 0;
}