#include <bits/stdc++.h>
#define MAXN 100000

int v[1 + MAXN];
int main(){
    FILE*fi,*fo;
    fi = fopen("cautbin.in","r");
    fo = fopen("cautbin.out","w");

    int n, m;
    fscanf(fi,"%d", &n);
    for(int i = 1; i <= n; i++) fscanf(fi,"%d", &v[i]);
    fscanf(fi,"%d", &m);
    for(int z = 1; z <= m; z++){
        int t, x;
        fscanf(fi,"%d%d", &t, &x);
        if(t == 0){
            int st = 1, dr = n;
            while(dr - st > 1){
                int m = (st + dr) / 2;
                if(v[m] > x) dr = m - 1;
                else st = m;
            }
            if(v[dr] == x) fprintf(fo,"%d\n", dr);
            else if(v[st] == x) fprintf(fo,"%d\n", st);
            else fprintf(fo,"-1\n");
        }
        else if(t == 1){
            int st = 1, dr = n;
            while(dr - st > 1){
                int m = (st + dr) / 2;
                if(v[m] > x) dr = m - 1;
                else st = m;
            }
            if(v[dr] <= x) fprintf(fo,"%d\n", dr);
            else if(v[st] <= x) fprintf(fo,"%d\n", st);
            else fprintf(fo,"-1\n");
        }
        else{
            int st = 1, dr = n;
            while(dr - st > 1){
                int m = (st + dr) / 2;
                if(v[m] < x) st = m + 1;
                else dr = m;
            }
            if(v[st] >= x) fprintf(fo,"%d\n", st);
            else if(v[dr] >= x) fprintf(fo,"%d\n", dr);
            else fprintf(fo,"-1\n");
        }
    }

    return 0;
}