#include <fstream>
#include <vector>
#define inf 100001
#define max(a, b) ((a) < (b) ? (b) : (a))
#define min(a, b) ((a) < (b) ? (a) : (b))
using namespace std;

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

vector<int> v;
int n;
bool gasit = false;

int cautareBinara0(int st, int dr, int x, int j)
{
    int mij = st + (dr - st) / 2;
    if (st <= dr)
    {
        if (x < v[mij])
            return cautareBinara0(st, mij - 1, x, j);
        else if (x > v[mij])
            return cautareBinara0(mij + 1, dr, x, j);
        else if (x == v[mij])
        {
            if (j < 2)
                return max(mij + 1, cautareBinara0(mij + 1, dr, x, j));
            if (j == 2)
            {
                gasit = true;
                return min(mij + 1, cautareBinara0(st, mij - 1, x, j));
            }
        }
    }
    if (j == 0)
        return -1;
    else if (j == 1)
        return dr + 1;
    else
    {
        if (gasit)
            return inf;
        else
            return dr;
    }
}

int main()
{
    int m;
    f >> n;
    v.resize(n);
    for (int i = 0; i < n; ++i)
        f >> v[i];
    f >> m;
    for (int i = 0; i < m; ++i)
    {
        int j, x;
        f >> j >> x;
        gasit = false;
        g << cautareBinara0(0, n - 1, x, j) << "\n";
    }
    return 0;
}