#include <cstdio>
#include <climits>

#define MAXN 100002

using namespace std;

FILE *f, *g;

int stare, v[MAXN], x, n, m, nr;

int BinarySearch(int st, int dr)
{
    if (st <= dr)
    {
        int mij = (st + dr) / 2;
        if (v[mij] == x)
            return mij;
        else if (v[mij] < x)
            BinarySearch(mij + 1, dr);
        BinarySearch(st, mij - 1);
    }
    if (stare == 1)
        return dr;
    else if (stare == 2)
        return st;
    else
        return -1;
}

void Read()
{
    fscanf(f, "%d", &n);

    for (int i = 1; i <= n; i++)
    {
        fscanf(f, "%d", &v[i]);
    }

    fscanf(f, "%d", &m);

    for (int i = 1; i <= m; i++)
    {
       fscanf(f, "%d %d", &stare, &x);

       nr = BinarySearch(1, n);

       if (nr == -1)
       {
           fprintf(g, "%d\n", -1);
           continue;
       }
       if (stare == 0)
       {
           while (v[nr] == x)
                nr++;
            nr--;
       }
       else if (stare == 1)
       {
           if (v[nr] == x) {
            while (v[nr] == x)
                    nr++;
            nr--;
           }
       }
       else
       {
           if (v[nr] == x)
           {
               while (v[nr] == x)
                    nr--;
                nr++;
           }
       }
        fprintf(g, "%d\n", nr);
    }
}

int main ()
{
    f = fopen("cautbin.in", "r");
    g = fopen("cautbin.out", "w");

    Read();

    fclose(f); fclose(g); return 0;
}