#include <bits/stdc++.h>

using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int n, v[100010];

signed main()
{
    fin >> n;
    for(int i=1; i<=n; i++) fin >> v[i];
    int tt; fin >> tt;
    while(tt--) {
        int tip, x; fin >> tip >> x;
        if(tip == 0) {
            int st = 1, dr = n, sol = -1;
            while(st <= dr) {
                int mid = (st + dr) / 2;
                if(v[mid] == x) sol = mid, st = mid + 1;
                else if(v[mid] < x) st = mid + 1;
                else dr = mid - 1;
            }
            fout << sol << '\n';
        }
        else if(tip == 1) {
            int st = 1, dr = n, sol = -1;
            while(st <= dr) {
                int mid = (st + dr) / 2;
                if(v[mid] <= x) sol = mid, st = mid + 1;
                else dr = mid - 1;
            }
            fout << sol << '\n';
        }
        else {
            int st = 1, dr = n, sol = -1;
            while(st <= dr) {
                int mid = (st + dr) / 2;
                if(v[mid] >= x) sol = mid, dr = mid - 1;
                else st = mid + 1;
            }
            fout << sol << '\n';
        }
    }

    return 0;
}