#include <fstream>
#include <vector>

using namespace std;


ifstream cin("cautbin.in");
ofstream cout("cautbin.out");

int main(void) {
    
    int n, m;
    cin >> n;
    vector<int> v(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> v[i];
    
    cin >> m;
    while (m--) {
        int c, x;
        cin >> c >> x;
        switch (c) {
            case 0:
            {
                int st = 1, dr = n;
                int ans = -1;

                while (st <= dr) {
                    int mid = st + (dr - st) / 2;
                    if (x >= v[mid]) {
                        ans = mid;
                        st = mid + 1;
                    } else {
                        dr = mid - 1;
                    }
                }
                if (ans > n || v[ans] != x)
                    cout << -1 << endl;
                else
                    cout << ans << endl;
                break;
            }
            case 1:
            {
                int st = 1, dr = n;
                int ans = -1;

                while (st <= dr) {
                    int mid = st + (dr - st) / 2;
                    if (x >= v[mid]) {
                        ans = mid;
                        st = mid + 1;
                    } else {
                        dr = mid - 1;
                    }
                }
                cout << ans << endl;
                break;
            }
            case 2:
            {
                int st = 1, dr = n;
                int ans = -1;

                while (st <= dr) {
                    int mid = st + (dr - st) / 2;
                    if (x <= v[mid]) {
                        ans = mid;
                        dr = mid - 1;
                    } else {
                        st = mid + 1;
                    }
                }

                cout << ans << endl;
                break;
            }
            default:
            {
                break;
            }
        }
    }
}