#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

int n;

int binary_search(vector <int> array, int to_find, int method)
{
    int left = 0, right = n-1;
    while(left < right)
    {
        int mid = (left + right) / 2;
        if(array[mid] < to_find)
            left = mid + 1;
        else if(array[mid] == to_find && method != 2)
            left = mid + 1;
        else
            right = mid-1;
    }
    return right;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    ifstream cin ("cautbin.in");
    ofstream cout("cautbin.out");
    int questions, a, b;
    cin >> n;
    vector <int> array(n);
    for(int i = 0; i < n; i++)
        cin >> array[i];
    cin >> questions;
    for(int i = 0; i < questions; i++)
    {
        cin >> a >> b;
        int pos = binary_search(array, b, a);
        switch(a)
        {
            case 0:
                if(array[pos - 1] == b)
                    cout << pos << '\n';
                else
                    cout << -1 << '\n';
                break;
            case 1:
                cout << pos << '\n';
                break;
            case 2:
                cout << pos + 1 << '\n';
                break;
            default:
                break;
        }
    }
    return 0;
}