#include <fstream>
using namespace std;

ifstream f("cautbin.in");
ofstream f2("cautbin.out");

int a[100001], mid, N, i, x, optiune, M, lb, ub;

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


int main()
{
    f >> N;
    for(i = 1; i <= N; ++i){
        f >> a[i];
    }
    f >> M;
    for(i = 1; i <= M; ++i){
        f >> optiune >> x;
        if(optiune == 0){
            cautareBinara(x);
            if(a[mid] == x){
                while(a[mid + 1] == x){
                    mid++;
                }
                f2 << mid << endl;
            }
            else{
                f2 << -1 << endl;
            }
        }
        if(optiune == 1){
            cautareBinara(x);
            if(a[mid] == x){
                while(a[mid + 1] == x){
                    mid++;
                }
            }
            else if(a[mid] > x){
                mid--;
            }
            f2 << mid << endl;
        }
        if(optiune == 2){
            cautareBinara(x);
            if(a[mid] == x){
                while(a[mid - 1] == a[mid]){
                    mid--;
                }
            }
            else if(a[mid] < x){
                mid++;
            }
            f2 << mid << endl;
        }
    }

    return 0;
}