#include <fstream>
#include <vector>

using namespace std;

ifstream be("cautbin.in");
ofstream ki("cautbin.out");

int bin0(const vector<int> &v, const int &x, int bal, int jobb)
{
    if(bal > jobb)
    {
        return -1;
    }

    int kozep = (bal + jobb) / 2;
    
    if(v[kozep] == x)
    {
        int res = bin0(v, x, kozep + 1, jobb);

        if(res == -1)
        {
            return kozep + 1;
        }
        
        return res;
    }

    if(v[kozep] < x)
    {
        return bin0(v, x, kozep + 1, jobb);
    }else
    {
        return bin0(v, x, bal, kozep - 1);
    }
    
}

int bin1(const vector<int> &v, const int &x, int bal, int jobb)
{
    if(bal > jobb)
    {
        return -1;
    }

    int kozep = (bal + jobb) / 2;
    
    if(v[kozep] <= x)
    {
        int res = bin1(v, x, kozep + 1, jobb);

        if (res == -1)
        {
            return kozep + 1;
        }

        return res;

    }else
    {
        return bin1(v, x, bal, kozep - 1);
    }
}

int bin2(const vector<int> &v, const int &x, int bal, int jobb)
{
    if(bal > jobb)
    {
        return -1;
    }

    int kozep = (bal + jobb) / 2;
    
    if(v[kozep] >= x)
    {
        int res = bin2(v, x, bal, kozep - 1);

        if (res == -1) 
        {
            return kozep + 1;
        }

        return res;
    }else
    {
        return bin2(v, x, kozep + 1, jobb);
    }
}

void answer(const vector<int> &v, const int &t, const int &x)
{
    int eredmeny;
    int jobb = v.size() - 1;

    if(t == 0)
    {
        eredmeny = bin0(v, x, 0, jobb);
    }else if(t == 1)
    {
        eredmeny = bin1(v, x, 0, jobb);
    }else
    {
        eredmeny = bin2(v, x, 0, jobb);
    }

    ki << eredmeny << "\n";
}

int main()
{
    int n;
    be >> n;

    vector<int> v(n);

    for(int i = 0; i < n; i++)
    {
        be >> v[i];
    }

    int m;
    be >> m;

    for(int i = 0; i < m; i++)
    {
        int t, x;
        be >> t >> x;

        answer(v, t, x);
    }

    return 0;
}