#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
vector <long> v;

int cautbin (int q, int nr,int n)
{
int i=1, j=n;
switch (q)
{
    case 0:
        while (i<j)
            if (v[(i+j)/2]>nr)
                j=(i+j-1)/2; else
                i=(i+j+1)/2;
        if (v[i-1]==nr)
        return i-1;
        return -1;
        break;
    case 1:
        while (i<j)
            if (v[(i+j)/2]>nr)
                j=(i+j-1)/2; else
                i=(i+j+1)/2;
        if (v[i-2]==nr && v[i-1]!=nr)
        return i-2;
        return i-1;
        break;
    default:
         while (i<j)
            if (v[(i+j)/2]>=nr)
                j=(i+j-1)/2; else
                i=(i+j+1)/2;
        return i;
        break;
}
}

int main()
{
    ifstream f ("cautbin.in");
    ofstream g ("cautbin.out");
    long n, m;
    f>>n;
    v.push_back(-1);
    for (int i = 1; i <= n; i++)
        {
            int p;
            f>>p;
            v.push_back(p);
        }
    f>>m;
    int q, nr;
    for (int i = 1; i<=m; i++)
    {
        f>>q>>nr;
        g<<cautbin(q, nr,n)<<"\n";
    }
    return 0;
}