#include <fstream>

using namespace std;
ifstream cin("cautbin.in");
ofstream cout("cautbin.out");
int n, v[100005], vt, i, mij;
int f0(int left, int right, int v[], int val)
{
    int mij=left + (right - left) / 2;
    while(left <= right)
    {
        if(v[mij] <= val)
        {
            left = mij+1;
        }
        else
            right = mij-1;
        mij = left + (right - left) / 2;
    }
    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=left + (right - left) / 2;
    while(left < right)
    {
        mij = left + (right - left) / 2;
        if(v[mij] <= val)
        {
            left = mij + 1;
        }
        else
            right = mij;
        mij = left + (right - left) / 2;
    }
   mij=left + (right - left) / 2;
   if(v[mij] > val)
        mij--;
   return mij;
}
int f2(int left, int right, int v[], int val)
{
    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 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;
}