#include <stdio.h>
#include <stdlib.h>
#define MAXN 10001


int N,M,v[MAXN],mid,st,dr,a,nr;

void cit(){

}
int cautbin_0(int nr){
    st = 1,dr = N;
    while(st <= dr){

        mid = (st + dr)/2;

        if(v[mid] > nr){
            dr = mid - 1;
        }else if(v[mid] <= nr){
            st = mid  + 1;
        }
    }
    mid = (st + dr)/2;
    if(v[mid + 1] == nr){
        return mid + 1;
    }else if(v[mid] == nr){
        return mid;
    }else{
        return -1;
    }
}
int cautbin_1(int nr){
    st = 1,dr = N;
    while(st <= dr){

        mid = (dr + st)/2;
        if(v[mid] > nr){
            dr = mid - 1;
        }else if(v[mid] <= nr){
            st = mid  + 1;
        }
    }
    mid = (st + dr)/2;
    if(v[mid + 1] <= nr && v[mid+1]){
        return mid + 1;
    }else if(v[mid] <= nr ){
        return mid;
    }
}
int cautbin_2(int nr){
    st = 1,dr = N;
    while(st <= dr){

        mid = (st + dr)/2;
        if(v[mid] >= nr){
            dr = mid - 1;
        }else if(v[mid] < nr){
            st = mid  + 1;
        }
    }
    mid = (st + dr)/2;
    if(v[mid+1] >= nr){
        return mid+1;
    }else if(v[mid] >= nr){
        return mid;
    }
}

int main()
{   freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);

    scanf("%d",&N);
    for(int i = 1 ; i <= N; i ++){
        scanf("%d",&v[i]);
    }
    scanf("%d",&M);

    for(int i = 1 ; i <= M; i ++){

        scanf("%d%d",&a,&nr);
        if(a == 0){
            printf("%d\n",cautbin_0(nr));
        }else if(a == 1){
            printf("%d\n",cautbin_1(nr));
        }else{
            printf("%d\n",cautbin_2(nr));
        }
    }
    return 0;
}