#include <fstream>
#include <vector>
using namespace std;

ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

int binarySearch0(vector<int> v, int n, int numar);
int binarySearch1(vector<int> v, int n, int numar);
int binarySearch2(vector<int> v, int n, int numar);

int main()
{
    int n, x;
    vector <int> v;
    fin >> n;
    v.push_back(0);
    for(int i = 0; i < n; i++)
    {    
        fin >> x;
        v.push_back(x);
    }
    int m, metoda, numar;
    fin >> m;
    for(int j = 0; j < m; j++)
    {
        fin >> metoda >> numar;
        switch (metoda)
        {
        case 0:
            fout << binarySearch0(v, n, numar) << '\n';
            break;
        case 1:
            fout << binarySearch1(v, n, numar) << '\n';
            break;
        
        case 2:
            fout << binarySearch2(v, n, numar) << '\n';
            break;
        default:
            break;
        }
    }

    return 0;
}



int binarySearch0(vector<int> v, int n, int numar)
{
    int left = 1;
    int right = n;

    while (left <= right)
    {
        int middle = (left + right) / 2;
        if(v[middle] == numar && v[middle + 1] > numar)
            return middle;
        else if(numar < v[middle])
                right = middle - 1;
            else 
                left = middle + 1;
    }
    return -1;
}

int binarySearch1(vector <int> v, int n, int numar)
{
    int left = 1;
    int right = n;
    while(left <= right)
    {
        int middle = (left + right) / 2;
        if(v[middle] <= numar && v[middle + 1] > numar)
        {
            return middle;
        }
        else 
            if(v[middle] > numar)
                right = middle - 1;
            else 
                left = middle + 1;
    }
}

int binarySearch2(vector<int> v, int n, int numar) 
{
    int left = 1;
    int right = n;
    while(left <= right)
    {
        int middle = (left + right) / 2;
        if(v[middle - 1] < numar && v[middle] >= numar)
            {
            return middle;
            }
        else
            if(v[middle] >= numar)
                right = middle - 1;
            else
                left = middle + 1;
        
    }
}