#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <string>
#include <algorithm>
#include <iterator>
#include <iostream>
#include <cassert>
#include <stdio.h>
#include <cmath>
#include <iostream>
#include <fstream>
using namespace std;

int main() {

    ifstream input("cautbin.in");
    ofstream output("cautbin.out");
    cout << " start \n";
    int n = 0;
    input >> n;
    int d[n];
    for (int i = 0; i < n; i++) {
        input >> d[i];
    }
    int k;
    input >> k;
    for (int i = 0; i < k; i++) {
        int a, b;
        input >> a >> b;
        int left = 0;
        int right = n - 1;

            while (left <= right) {
                int mij =  left + (right - left) / 2;
                if (a == 0 || a == 1) {
                    if ( b>=d[mij] ) {
                        left = mij+1;
                    } else {
                        right = mij - 1;
                    }
                } else{
                    if (b>d[mij]) {
                        left = mij+1;
                    } else {
                        right = mij - 1;
                    }
                }
            }
            if (d[right] == b ) {
                output << right + 1 << "\n";
            } else {
                if (a == 0) {
                    output << "-1\n";
                }
                if (a == 1) {
                    output << right + 1 << "\n";
                }
                if (a == 2) {
                    output << right + 2 << "\n";

                }
            }
        
    }
    output.close();
    return 0;
}