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

using namespace std;

ifstream fin("cautbin.in");

int cautBin1(int val, int n, const vector<int>v)
{
    int left = 0;
    int right = n-1;
    int middle = (left+right)/2;
    bool found = 0;
    while(left <= right)
    {
        middle = (left + right) /2;
        if(val >= v[middle])
        {
            left = middle + 1;
            if(v[middle] == val)
                found = 1;
        }
        else right = middle - 1;
    }
    if(found == 1)
        return right;
    return -1;
}

int cautBin2(int val, int n, const vector<int>v)
{
    int left = 0;
    int right = n-1;
    int middle;
    while(left <= right)
    {
        middle = (left + right) /2;
        if(val >= v[middle])
            left = middle + 1;
        else right = middle - 1;
    }
    return right;
}

int cautBin3(int val, int n, const vector<int>v)
{
    int left = 0;
    int right = n-1;
    int middle;
    while(left <= right)
    {
        middle = (left + right) /2;
        if(val <= v[middle])
            right = middle -1;
        else left = middle +1 ;
    }
    return left;
}

int main()
{
    int n;
    vector <int> v;
    fin>>n;
    v.resize(n);
    for(int i=0; i<n; i++)
        fin>>v[i];

    int queryNr, query, nr;
    fin>>queryNr;
    for(int i=0; i<queryNr; i++)
    {
        fin>>query>>nr;
        if(query == 0)
            cout<<cautBin1(nr, n, v)+1<<'\n';
        else if(query == 1)
            cout<<cautBin2(nr, n, v)+1<<'\n';
        else if(query == 2)
            cout<<cautBin3(nr, n, v)+1<<'\n';
    }

    return 0;
}