#include <bits/stdc++.h>

using namespace std;

int v[100005];

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

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

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

int main()
{
    int n,m,type,x,i;
    int *poz;
    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",&type,&x);
        if(type == 0){
            printf("%d\n",binarySearch1(x, n));
        }else if(type == 1){
            printf("%d\n",binarySearch2(x, n));
        }else{
            printf("%d\n",binarySearch3(x-1, n));
        }
    }
    return 0;
}