#include <cstdio>

using namespace std;

int v[100001],n;

int bsearch0 (int x) {
    int i,pas;
    pas = 1 << 30;
    i = 0;
    while (pas) {
        if (i + pas < n && v[i + pas] == x)
            i += pas;
        pas /= 2;
    }
    if (i == 0)
        i = -2;
    return i;
}

int bsearch1 (int x) {
    int i,pas;
    pas = 1 << 30;
    i = 0;
    while (pas) {
        if (i + pas < n && v[i + pas] <= x)
            i += pas;
        pas /= 2;
    }
    return i;
}

int bsearch2 (int x) {
    int i,pas;
    pas = 1 << 30;
    i = n - 1;
    while (pas) {
        if (i - pas > 0 && v[i - pas] >= x)
            i -= pas;
        pas /= 2;
    }
    return i;
}

int main(){
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);
    int m,x,nr,i;
    scanf("%d",&n);
    for (i=0;i<n;i++)
        scanf("%d",&v[i]);
    scanf("%d",&m);
    for (i=0;i<m;i++) {
        scanf("%d%d",&nr,&x);
        if (nr == 0)
            printf("%d\n",bsearch0(x) + 1);
        else if (nr == 1)
            printf("%d\n",bsearch1(x) + 1);
        else
            printf("%d\n",bsearch2(x) + 1);
    }
    return 0;
}