#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)
    {
        int kozep = (bal + jobb + 1) / 2;
        
        if(v[kozep] <= x)
        {
            return bin0(v, x, kozep + 1, jobb);
        }else
        {
            return bin0(v, x, bal, kozep - 1);
        }
    }

    if(v[bal] == x)
    {
        return bal + 1;
    }

    return -1;
}

int bin1(const vector<int> &v, const int &x, int bal, int jobb)
{
    if(bal <= jobb && v[(bal + jobb + 1) / 2] <= x)
    {
        int kozep = (bal + jobb) / 2;
        
        if(v[kozep] <= x)
        {
            return bin1(v, x, kozep + 1, jobb);
        }else
        {
            return bin1(v, x, bal, kozep - 1);
        }
    }

    return bal + 1;
    
}

int bin2(const vector<int> &v, const int &x, int bal, int jobb)
{
    if(bal <= jobb && v[(bal + jobb + 1) / 2] >= x)
    {
        int kozep = (bal + jobb) / 2;
        
        if(v[kozep] >= x)
        {
            return bin2(v, x, bal, kozep - 1);
        }else
        {
            return bin2(v, x, kozep + 1, jobb);
        }
    }

    return bal + 1;
    
}

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;
}