#include <iostream>
using namespace std;

int a[100001];

int main()
{
    int N;
    cin >> N;

    for (int i = 1; i <= N; i++)
        cin >> a[i];

    int M;
    cin >> M;

    while (M)
    {
        int tip;
        int x;
        cin >> tip >> x;

        int st = 1, dr = N;
        int poz = 0;

        while (st <= dr && tip==0)
        {
            int mij = (st + dr ) / 2;
            if (a[mij] == x)
            {
                poz = mij;
                st = mij + 1;
            }
            else if (a[mij] < x)
            {
                st = mij + 1;
            }
            else
            {
                dr = mij - 1;
            }
        }
        cout << poz << "\n";



    if (tip == 1)
    {
        while (st <= dr)
        {
            int mij = (st + dr ) / 2;
            if (a[mij] <= x)
            {
                poz = mij;
                st = mij + 1;
            }
            else
            {
                dr = mij - 1;
            }
        }
        cout << poz << "\n";
    }

    if (tip == 2)
    {
        while (st <= dr)
        {
            int mij =(st + dr ) / 2;
            if (a[mij] >= x)
            {
                poz = mij;
                dr = mij - 1;
            }
            else
            {
                st = mij + 1;
            }
        }
        cout << poz << "\n";

    }M--;
    }
    return 0;
}