#include <iostream>
#include <fstream>
using namespace std;
ifstream fin ("cautbin.in");
ofstream fout ("cautbin.out");
int v[100001];
int main()
{
    int n;
    fin >> n;
    for (int i = 1; i <= n; i++)
        fin >> v[i];
    int q;
    fin >> q;
    for (int i = 1; i <= q; i++)
    {
        int tip, x;
        fin >> tip >> x;
        if (tip == 0)
        {
            int p = 1, u = n, rez = -1;
            while (p <= u)
            {
                int mij = (p + u) / 2;
                if (v[mij] == x)
                {
                    rez = mij;
                    p = mij + 1;
                }
                else if (v[mij] < x)
                {
                    p = mij + 1;
                }
                else
                {
                    u = mij - 1;
                }
            }
            fout << rez << '\n';
        }
        else if (tip == 1)
        {
            int p = 1, u = n, rez = 1;
            while (p <= u)
            {
                int mij = (p + u) / 2;
                if (v[mij] <= x)
                {
                    rez = mij;
                    p = mij + 1;
                }
                else
                {
                    u = mij - 1;
                }
            }
            fout << rez << '\n';
        }
        else
        {
            int p = 1, u = n, rez = n;
            while(p<=u)
            {
                int mij = (p + u) / 2;
                if(v[mij] >= x)
                {
                    rez = mij;
                    u = mij - 1;
                }
                else
                {
                    p = mij + 1;
                }
            }
            fout<<rez<<'\n';
        }
    }
    return 0;
}