#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#define N 100100

using namespace std;

int v[N];
int n,lo,hi,mid;

int cautbin_0(int x){

    while(lo<hi){
        mid=lo+(hi-lo)/2;
        if(x>v[mid]){
            lo=mid+1;
        }else if(x<v[mid]){
            hi=mid-1;
        }else{
            lo=mid;
            hi=mid;
        }
    }
    if(v[lo]!=x){
        return -1;
    }
    while(v[lo+1]==x && lo+1<=n){
        lo++;
    }
    return lo;

}

int cautbin_1(int x){

    while(lo<hi){
        mid=lo+(hi-lo)/2;
        if(x>=v[mid]){
            lo=mid+1;
        }else if(x<v[mid]){
            hi=mid;
        }
    }

    if(v[lo]>x){
        lo--;
    }
    return lo;

}

int cautbin_2(int x){

    while(lo<hi){
        mid=lo+(hi-lo)/2;
        if(x>v[mid]){
            lo=mid+1;
        }else if(x<=v[mid]){
            hi=mid;
        }
    }

    if(v[lo]<x){
        lo++;
    }
    return lo;

}

int main(){
    int i,p,x,m;

    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=0;i<m;i++){
        scanf("%d%d",&p,&x);
        lo=1;
        hi=n;
        if(p==0){
            printf("%d\n",cautbin_0(x));
        }else if(p==1){
            printf("%d\n",cautbin_1(x));
        }else{
            printf("%d\n",cautbin_2(x));
        }
    }

    return 0;
}