#include <bits/stdc++.h>

using namespace std;

ifstream f("cautbin.in");
ofstream g("cautbin.out");

int n, m, x, t;
vector<int> v;

int cbin1(int left, int right, int val)
{
    if (left == right)
        return v[left] == val ? left : -1;

    int mid = left + (right - left) / 2;
    if (val < v[mid])
        return cbin1(left, mid, val);
    else
        return max(
            v[mid] == val ? mid : -1,
            cbin1(mid + 1, right, val));
}

int cbin2(int left, int right, int val)
{
    if (left >= right)
        return left;

    int mid = left + (right - left) / 2;
    if (val < v[mid])
        return cbin2(left, m - 1, val);
    else 
        if(val == v[mid])
        {
            int next = cbin2(mid + 1, right, val);
            if (v[next] == val)
                return next;
            else
                return mid;
        }
        else
        {
            return cbin2(mid + 1, right, val);
        }
}

int cbin3(int left, int right, int val)
{
    if (left >= right)
        return left;
    // 1 3 3 3 5

    int mid = left + (right - left) / 2;
    if (v[mid] < val)
        return cbin3(mid + 1, right, val);
    else
        if (v[mid] == val)
        {
            int next = cbin3(left, mid - 1, val);
            if (v[next] == val)
                return next;
            else
                return mid;
        }
        else
        {
            return cbin3(left, mid - 1, val);
        }
}

int main()
{
    f >> n;
    v.push_back(0);

    for (int i = 0; i < n; ++i)
        f >> x,
        v.push_back(x);

    f >> m;
    while (m--)
    {
        f >> t >> x;
        if (t == 0)
            g << cbin1(1, n, x) << '\n';
        if (t == 1)
            g << cbin2(1, n, x) << '\n';
        if (t == 2)
            g << cbin3(1, n, x) << '\n';
    }

    return 0;
}