#include <iostream>

int BinarySearch(int l, int r, int x, int a[], bool LesserFlag);
int Instr0(int x, int n, int a[]);
int Instr1(int x, int n, int a[]);
int Instr2(int x, int n, int a[]);

int a[100000];
std::ifstream IN("cautbin.in");
std::ofstream OUT("cautbin.out");
int main()
{
    int n;
    IN >> n;

    for (int i = 0; i < n; ++i) IN >> a[i];

    int instr;
    IN >> instr;

    int ins, x;
    for (int i = 0; i < instr; ++i)
    {
        IN >> ins >> x;
        switch(ins)
        {
        case 0:
            OUT << Instr0(x, n, a);
            break;
        case 1:
            OUT << Instr1(x, n, a);
            break;
        case 2:
            OUT << Instr2(x, n, a);
            break;
        }

        OUT << '\n';
    }
}

int BinarySearch(int l, int r, int x, int a[], bool LesserFlag)
{
    int m;
    while(l <= r)
    {
        m = (l + r) / 2;
        if(x == a[m])
            return m;
        if(x > a[m])
            l = m + 1;
        if(x < a[m])
            r = m - 1;
    }
    if (LesserFlag) return r;
    return -1;
}

int Instr0(int x, int n, int a[])
{
    int pos = BinarySearch(0, n-1, x, a, false);
    if (pos == -1) return -1;

    while(a[pos + 1] == x) pos++;
    return pos + 1;
}

int Instr1(int x, int n, int a[])
{
    int pos = BinarySearch(0, n-1, x, a, true);
    if (a[pos] != x) return pos;

    while(a[pos + 1] == x) pos++;
    return pos + 1;
}

int Instr2(int x, int n, int a[])
{
    int pos = BinarySearch(0, n-1, x, a, true);
    if (a[pos] != x) return pos + 2;

    for (int i = pos; i > 0; i--)
    {
        if (a[pos - 1] == x) pos--;
        else return pos + 1;
    }
}