#include <iostream>
#include <fstream>
using namespace std;

ifstream f1("cautbin.in");
ofstream f2("cautbin.out");
int N;
int a[100001];
int M;
int mid, lb, ub, i, optiune, x;



void catareBinara(int x){
    lb = 1;
    ub = N;
    while(lb <= ub){
        mid = lb + (ub - lb) / 2;
        if(a[mid] == x){
            break;
        }
        if(a[mid] > x){
            ub = mid - 1;
        }
        if(a[mid] < x){
            lb = mid + 1;
        }
    }
}


int main()
{
    f1 >> N;
    for(i = 1; i <= N; i++){
        f1 >> a[i];
    }
    f1 >> M;

    for(i = 1; i <= M; i++){
        f1 >> optiune >> x;
        if(optiune == 0){
            catareBinara(x);
            if(a[mid] == x){
                while(a[mid + 1] == x){
                    mid++;
                }
                f2 << mid << endl;
            }
            else{
                f2 << -1 << endl;
            }
        }
        if(optiune == 1){
            catareBinara(x);
            if(a[mid] == x){
                while(a[mid + 1] == x){
                    mid++;
                }
            }
            else if(a[mid] > x)
                mid--;
            f2 << mid << endl;
        }
        if(optiune == 2){
            catareBinara(x);
            if(a[mid] == x){
                while(a[mid - 1] == a[mid]){
                    mid--;
                }
            }
            else if(a[mid] < x)
                mid++;
            f2 << mid << endl;
        }
    }
    return 0;
}