#include <stdio.h>
#include <stdlib.h>
#define N 100010
int n,v[N];
int solve0(int val){    	
        int low = 0;
        int high = n - 1;
        while ((low != high) && ((low + 1 != high))) {
            int med = low + (high - low) / 2;
            if (val == v[med]) {
                low = med;
            } else if (val > v[med]) {
                low = med;
            } else {
                high = med;
            }
        }
        if (v[high] == val) {
            return high + 1;
        }
        if (v[low] == val) {
            return low + 1;
        }
        return -1;
}
int solve1(int val){
        int low = 0;
        int high = n - 1;
        while ((low != high) && ((low + 1 != high))) {
            int med = low + (high - low) / 2;
            if (val < v[med]) {
                high = med;
            } else {
                low = med;
            }
        }
        if (low == high) return high + 1;
        if (v[high] <=  val) return high + 1;
        else return low + 1;
}
int solve2(int val){
        int low = 0;
        int high = n - 1;
        while ((low != high) && ((low + 1 != high))) {
            int med = low + (high - low) / 2;
            if (val > v[med]) {
                low = med;
            } else {
                high = med;
            }
        }
        if (low == high) return high + 1;
        if (v[low] >=  val) return low + 1;
        else return high + 1;
}
int main(){
    int i,m,val,tip;
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);
    scanf("%d",&n);
    for (i=0;i<n;++i)
        scanf("%d",&v[i]);
    scanf("%d",&m);
    while (m--){
          scanf("%d%d",&tip,&val);
          if (tip==0)
             printf("%d\n",solve0(val));
          if (tip==1)
             printf("%d\n",solve1(val));
          if (tip==2)
             printf("%d\n",solve2(val));
    }          
    exit(0);
}