#include <fstream>
#include <iostream>
using namespace std;
ifstream in("cautbin.in");
ofstream out("cautbin.out");
const int nmax = 1e5;
int v[nmax+5];

int cBin(int st, int x, int dr)
    {
    int mid;
    while(st <= dr){
        mid = (st + dr) / 2;
        if(x == v[mid])
            return mid;
        else if(x < v[mid])
            dr = mid - 1;
        else st = mid + 1;
    }
    return st;
    }

int main()
{

    int n;
    in >> n;

    for (int i = 1; i <= n; ++i)
    {
        in >> v[i];
    }
    int m;
    in >> m;
    for (int i = 1; i <= m; ++i)
    {
        int q, x;
        in >> q >> x;


        if (q == 0)
        {
            int pos=cBin(1, x, n);

            while(v[pos]==v[pos+1])
                pos++;

            if(v[pos]!= x)
                out<<-1<<'\n';
            else out<<pos<<'\n';
        }

        else if (q == 1)
        {
            int pos=cBin(1, x, n);

            if(v[pos]!=x)
                pos--;

            out << pos << '\n';
        }

        else
        {
            int pos=cBin(1, x, n);
            if(v[pos]==x)
                while(v[pos]==v[pos - 1])
                    pos--;
            out <<pos <<'\n';
        }
    }
    return 0;
}