#include <iostream>
#include <fstream>
using namespace std;

int N, M;
int i, x, v[100002], c, st, dr, mid;
bool gasit = false;
int main () {
    
    ifstream fin("cautbin.in");
    ofstream fout("cautbin.out");
    
    fin >> N;
    for (i = 1; i <= N; i++)    fin >> v[i];
    fin >> M;
    for (i = 1; i <= M; i++)
    {
        fin >> c >> x;
        st = 1;   dr = N;
        if (c == 0)
        {
            gasit = false;
            while (st <= dr && gasit == false)
            {
                mid = st + (dr-st)/2;
                if (v[mid] == x)   gasit = true;
                if (v[mid] < x)    st = mid+1;
                else if (v[mid] > x)   dr = mid-1;
            }
            //2 4 10 13 15 18 19 20 21 24
            if (gasit == true)
            {
                st = 1;     dr = N;
                while (st <= dr)
                {
                    mid = st + (dr-st) / 2;
                    if (v[mid] <= x)    st = mid+1;
                    else if (v[mid] > x)     dr = mid-1;
                    if (v[mid+1] != x && v[mid] == x)     {   st = dr+1;    fout << mid << "\n";   }
                }
            }
            else fout << -1 << "\n";
        }
        
        if (c == 1)
        {
            while (st <= dr)
            {
                mid = st + (dr-st) / 2;
                if (v[mid] <= x)    st = mid+1;
                if (v[mid] > x)     dr = mid-1;
                if ((v[mid+1] > x && v[mid] <= x) || mid == N)   {   st = dr+1;   fout << mid << "\n";   }
            }
        }
        if (c == 2)
        {
            while (st <= dr)
            {
                mid = st + (dr-st) / 2;
                if (v[mid] >= x)     dr = mid-1;
                else if (v[mid] < x)  st = mid+1;
                if (v[mid] >= x && v[mid-1] < x)  {   st = dr+1;   fout << mid << "\n";   }
            }
        }
    }
}
/*
 0 x - cea mai mare pozitie pe care se afla un element cu valoarea x sau -1 daca aceasta valoare nu se gaseste in sir
 1 x - cea mai mare pozitie pe care se afla un element cu valoarea mai mica sau egala cu x in sir. Se garanteaza ca cel mai mic numar al sirului este mai mic sau egal decat x
 2 x - cea mai mica pozitie pe care se afla un element cu valoarea mai mare sau egala cu x in sir. Se garanteaza ca cel mai mare numar din sir este mai mare sau egal decat x */