#include <cstdio>
#include <algorithm>
using namespace std;
#define LMAX 100005
int v[LMAX];
int main(){
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);
    int n,m,x,T;
    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",&T,&x);
        if(T==0){
            int p=upper_bound(v+1,v+n+1,x)-(v+1);
            if(v[p]!=x) printf("-1\n");
            else printf("%d\n",p);
        }
        else if(T==1){
            int p=upper_bound(v+1,v+n+1,x)-(v+1);
            printf("%d\n",p);
        }
        else if(T==2){
            int p=lower_bound(v+1,v+n+1,x)-(v+1);
            printf("%d\n",p+1);
        }
    }
}