#include <stdio.h>

using namespace std;

int v[100005];

int caut0(int,int,int);
int caut1(int,int,int);
int caut2(int,int,int);

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

int caut0 (int p, int u, int key) {
    int m;

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

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

int caut1 (int p, int u, int key) {
    int m, n = u;

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

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

int caut2 (int p, int u, int key) {
    int m;

    while (p < u) {
        m = (p + u) / 2;
        if (v[m] < key)
            p = m + 1;
        else
            u = m;
    }
    
    m = (p + u) / 2;
    if (v[m] < key)
       ++ m;
    return m;
}