#include <fstream>

using namespace std;

ifstream cin("cautbin.in");
ofstream cout("cautbin.out");
int v[100005], n;

int f0(int left, int right, int v[], int val)
{
    int mij;
    while (left <= right)
    {mij = left + (right - left) / 2;
    if(mij <= val)
        left = mij + 1;
    else
        right = mij -1;
    }
    mij = left + (right - left)  / 2;
    if(v[mij] > val)
        mij --;
    if(v[mij] == val)
        return mij;
    return -1;
}

int f1(int left, int right, int v[], int val)
{
    int mij;
    while(left < right)
    {
        mij = left + (right - left) / 2;
        if(v[mij] <= val)
             left = mij + 1;
        else
            right  = mij;
    }
    mij = left + (right - left) / 2;
    if(v[mij] > val)
        mij--;
    return mij;
}

int f2(int left, int right, int v[], int val)
{
    int mij;
    while( left < right)
    {
        mij = left + (right - left) / 2;
        if(v[mij] < val)
            left = mij + 1;
        else
            right = mij;
    }
    mij = left + (right - left) / 2;
    if(v[mij] < val)
        mij++;
    return mij;
}
int main()
{int i, vt, val,tests;
cin  >> n;
for(i = 1; i <= n; i++)
    cin >> v[i];
cin >> tests;
for(i = 1; i <= tests; i++)
{
    cin >> vt >> val;
    if(vt == 0)
        cout << f0(1,n,v,val) << "\n";
    else
        if(vt == 1)
        cout << f1(1,n,v,val) << "\n";
    else
        cout << f2(1,n,v,val) << "\n";
}

    return 0;
}