#include <cstdio>
#include <algorithm>
using namespace std;
#define MAX 100001

int n,a[MAX];

int cb0(int x){
    int l = 1, r = n, m;
    while(r-l > 1)
    {
        m = (l+r)/2;
        if( a[m] <= x ) l = m; else r = m - 1;
    }
    return a[r] == x ? r : a[l] == x ? l : -1;
}

int cb1(int x){
    int l = 1, r = n, m;
    while(r-l > 1)
    {
        m = (l+r)/2;
        if( a[m] > x ) r = m - 1; else l = m;
    }
    return a[r] <= x ? r : l;
}

int cb2(int x){
    int l = 1, r = n, m;
    while(r-l > 1)
    {
        m = (l+r)/2;
        if( a[m] < x ) l = m + 1; else r = m;
    }
    return a[l] >= x ? l : r;
}

int main(){
    int m,c,x;
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d ",&a[i]);
    scanf("%d",&m);
    while(m--)
    {
        scanf("%d %d",&c,&x);
        switch(c){
            case 0: printf("%d\n",cb0(x));  break;
            case 1: printf("%d\n",cb1(x));  break;
            case 2: printf("%d\n",cb2(x));  break;
        }
    }
    return 0;
}