#include <bits/stdc++.h>

using namespace std;

int main() {
    ifstream cin("cautbin.in");
    ofstream cout("cautbin.out");
    
    int n, m, v[100000], x, cer;
    
    cin >> n;
    
    for (int i = 0; i < n; i++)
        cin >> v[i];
        
    cin >> m;
    
    for (int i = 0; i < m; i++) {
        cin >> cer >> x;
        int st = 0, dr = n - 1, mid;
            
        while (st <= dr) {
            mid = st + (dr - st) / 2;
                
            if (v[mid] == x)
                break;
                    
            if (v[mid] < x)
                st = mid + 1;
            else
                dr = mid - 1;
        }
        
        if (st == dr) {
            if (cer == 1)
                mid--;
            
            if (cer)
                cout << mid + 1 << '\n';
            else
                cout << -1 << '\n';
        } else {
            if (cer != 2)
                while (v[mid + 1] == v[mid])
                    mid++;
            else
                while (v[mid - 1] == v[mid])
                    mid--;
                    
            cout << mid + 1 << '\n';
        }
    }

    return 0;
}