#include <iostream>
using namespace std;

FILE * fout, * fin;

int main() {
    fin = fopen("cautbin.in","r");
    fout = fopen("cautbin.out","w");

    int N;
    int v[100003];
    int M;

    fscanf(fin,"%d",&N);

    for ( int i = 1; i <= N; i++ ){
        fscanf(fin,"%d",v+i);
    }

    fscanf(fin,"%d",&M);

    for ( int i = 0; i < M; i++ ){
        int op, num;
        fscanf(fin, "%d%d", &op, &num );
        int L = 1;
        int R = N;
        switch(op){
            case 0: {
                int mid;
                while (L <= R) {
                    mid = (L + R) / 2;
                    if (v[mid] <= num)
                        L = mid + 1;
                    else
                        R = mid - 1;
                }
                mid = (L + R) / 2;
                if (v[mid] > num) mid --;
                if (v[mid] == num){
                    fprintf(fout,"%d\n",mid);
                    break;
                }
                fprintf(fout,"-1\n",mid);
                break;
            }
            case 1:{
                int mid, n = R;
                while (L < R){
                    mid = (L + R) / 2;
                    if (v[mid] <= num)
                        L = mid + 1;
                    else
                        R = mid;
                }
                mid = (L + R) / 2;
                if (v[mid] > num)
                   -- mid;
                fprintf(fout,"%d\n",mid);
                break;
            }
            case 2:{
                int mid;
                while (L < R) {
                    mid = (L + R) / 2;
                    if (v[mid] < num)
                        L = mid + 1;
                    else
                        R = mid;
                }
                mid = (L + R) / 2;
                if (v[mid] < num)
                   ++ mid;
                fprintf(fout,"%d\n",mid);
                break;
            }
        }
    }

    fclose(fin);
    fclose(fout);
}