#include <iostream>
#include <fstream>
using namespace std;
ifstream in("cautbin.in");
ofstream out("cautbin.out");

int v[100001];

int main()
{
    int nr, mid = 0, l = 0, d = 0, x;
    in >> nr;

    for (int i = 1; i <= nr; i++)
    {
        in >> x;
        v[i] = x;
    }
    int nrCerinte, cerinta, k;
    in >> nrCerinte;

    for (int i = 1; i <= nrCerinte; i++)
    {
        in >> cerinta >> k;

        if (cerinta == 0)
        {
            bool found = 0;
            l = 1;
            d = nr;

            while (l < d)
            {
                mid = l + (d - l) / 2;
                if (v[mid] == k)
                {
                    found = 1;
                    while (v[mid] == k)
                    {
                        found = 1;
                        mid++;
                    }
                }
                if (v[mid] > k)
                    l = d;
                if (v[mid] < k)
                    d = l;
            }

            if (!found)
                out << -1 << '\n';
            else
                out << mid - 1 << '\n';
        }
        if (cerinta == 1)
        {
            l = 1;
            d = nr;

            while (l < d)
            {
                mid = l + (d - l) / 2;
                if (v[mid] == k)
                {
                    while (v[mid] <= k)
                    {
                        mid++;
                    }
                }
                if (v[mid] > k)
                    l = d;
                if (v[mid] < k)
                    d = l;
            }
            out << mid - 1 << '\n';
        }
        if (cerinta == 2)
        {
            l = 1;
            d = nr;

            while (l < d)
            {
                mid = l + (d - l) / 2;
                if (v[mid] == k)
                {
                    while (v[mid] >= k)
                    {
                        mid--;
                    }
                }
                if (v[mid] > k)
                    l = d;
                if (v[mid] < k)
                    d = l;
            }
            out << mid + 1 << '\n';
        }
    }

    return 0;
}