#include <bits/stdc++.h>

using namespace std;

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

int main(){
    int a[100001], n = 0, m = 0, caz = 0, x = 0, st = 0, dr = 0, mid = 0;
    f >> n;
    for (int i = 0; i < n; i++) f >> a[i];

    f >> m;

    for (int i = 0; i < m; i++){
        f >> caz >> x;

        if (caz == 0){
            st = 1;
            dr = n;
            while (st <= dr) {
                mid = (st + dr) / 2;
                if (a[mid] == x){
                    while (a[mid] == x) mid++;
                    break;
                }
                else
                    if (a[mid] < x)
                        st = mid + 1;
                    else
                        dr = mid - 1;
            }
            if(st <= dr) g << mid << '\n';
            else g << -1 << '\n';
        }
        else if (caz == 1){
            st = 1;
            dr = n;
            while (st <= dr) {
                mid = (st + dr) / 2;
                if (a[mid] == x){
                    while (a[mid] == x) mid++;
                    break;
                }
                else
                    if (a[mid] < x)
                        st = mid + 1;
                    else
                        dr = mid - 1;
            }
            g << mid << '\n';
        }

        else if (caz == 2){
            st = 1;
            dr = n;
            while (st <= dr) {
                mid = (st + dr) / 2;
                if (a[mid] == x){
                    while (a[mid] == x) mid--;
                    break;
                }
                else
                    if (a[mid] < x)
                        st = mid + 1;
                    else
                        dr = mid - 1;
            }
            g << mid + 2 << '\n';
        }
    }
}