#include <stdio.h>

using namespace std;

#define ll long long unsigned
#define pb push_back
#define mp make_pair

int v[100005];

int binarySearch(int st, int n, int x){
    st--;
    int i,step;
    for(step = 1;step <= n;step <<= 1);
    for(i = st;step;step >>= 1){
        if(i+step <= n && v[i+step] <= x){
            i += step;
        }
    }
    return i;
}

int main(){
    int n,m,i,p,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 == 0){
            p = binarySearch(1, n, x);
            if(v[p] != x){
                printf("-1\n");
            }else{
                printf("%d\n",p);
            }
        }else if(op == 1){
            p = binarySearch(1, n, x);
            printf("%d\n",p);
        }else{
            p = binarySearch(1, n, x-1)+1;
            printf("%d\n",p);
        }
    }
    return 0;
}