#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

int s[100010];
int len;
int doOp(int op, int param);

int main()
{
    int nrOp;

    fin >> len;

    for(int i=0; i<len; i++)
    {
        fin >> s[i];
    }

    fin >> nrOp;

    for(int i=0; i<nrOp; i++)
    {
        int op, param;
        fin >> op;
        fin >> param;
        fout << doOp(op,param) + 1 << endl;
    }


    return 0;
}

int doOp(int op, int param)
{
    switch (op)
    {
        // cea mai mare pozitie pe care se afla un element cu valoarea x sau -1 daca aceasta valoare nu se gaseste in sir
    case 0:
    {
        if(s[len-1]== param)
        {
            return len-1;
        }
        int lo=0;
        int hi=len-1;
        int mid;
        while(hi-lo > 1)
        {
            mid = lo + (hi-lo)/2;
            if(s[mid] > param)
                hi = mid;
            else lo = mid;
        }
        if(s[hi] == param)
            return hi;
        if(s[lo]==param)
            return lo;
        return -1;
    }
    // cea mai mare pozitie pe care se afla un element cu valoarea mai mica sau egala cu x in sir. Se garanteaza ca cel mai mic numar al sirului este mai mic sau egal decat x
    case 1:
    {
        int lo = 0;
        int hi = len-1;
        int mid;
        while (hi - lo > 1)
        {
            mid = lo + (hi - lo) / 2;
            if (s[mid] > param)
                hi = mid;
            else
                lo = mid;
        }
        if (s[hi] <= param)
            return hi;
        return lo;
    }
    // cea mai mica pozitie pe care se afla un element cu valoarea mai mare sau egala cu x in sir. Se garanteaza ca cel mai mare numar din sir este mai mare sau egal decat x
    case 2:
    {
        int lo = 0;
        int hi = len-1;
        int mid;
        while (hi - lo > 1)
        {
            mid = lo + (hi - lo) / 2;
            if (s[mid] < param)
                lo = mid;
            else
                hi = mid;
        }

        if (s[lo] >= param)
            return lo;
        return hi;
    }
    }
    return -199;
}