#include <fstream>
using namespace std;
ifstream fin ("cautbin.in");
ofstream fout ("cautbin.out");

int CautBin(int n, int x[], int nr);
int main()
{
    int n, x[100000];
    int xmax = 0;
    fin >> n;
    for ( int i = 0; i < n; ++i )
    {
        fin >> x[i];
        if ( x[i] > xmax)
            xmax = x[i];
    }

    int m, Cod, nr;
    fin>>m;
    int p;
    for ( int i = 1; i <= m; ++i)
    {

        fin >> Cod >> nr;
        p = CautBin(n, x, nr);
        switch (Cod)
        {
            case 0:{ if ( p == -1) fout << p <<'\n';
            else
            {
                while (p + 1 < n && x[p+1] == nr)
                ++p;
                fout << p + 1 << '\n';
            }
            break;
            };
            case 1:{
                        if ( p == -1)
                        {
                            nr--;
                            int nrm = CautBin(n, x, nr);
                            while (nrm == -1 && nr > 0)
                            {
                               nr--;
                               nrm = CautBin(n, x, nr);
                            }
                            if(nr > 0)
                            {
                                while ( nrm + 1 < n && x[nrm+1] == nr)
                                nrm++;
                                fout << nrm +1 << '\n';
                            }


                        }
                        else
                        {
                             while (p + 1 < n && x[p+1] == nr)
                                ++p;
                                fout << p + 1 << '\n';
                        }
                        break;
                    };
            case 2:{
                 if ( p == -1)
                        {
                            nr++;
                            int nrm = CautBin(n, x, nr);
                            while (nrm == -1 && nr <=xmax)
                            {
                               nr++;
                               nrm = CautBin(n, x, nr);
                            }
                            if(nr <= xmax)
                            {
                                while ( nrm + 1 < n && x[nrm+1] == nr)
                                nrm++;
                                fout << nrm +1 << '\n';
                            }

                        }
                        else
                        {
                             while (p - 1 >= 0 && x[p-1] == nr)
                                --p;
                                fout << p + 1 << '\n';
                        }

            };
        }

    }
    fin.close();
    fout.close();
    return 0;
}
int CautBin(int n, int x[], int nr)
{
    int s, d, m;
    s = 0;
    d = n-1;
    while(s <= d)
    {
        m = (s+d) / 2;
        if ( nr == x[m]) return m;
        else
        if (nr < x[m] )
            d = m - 1;
            else
            s = m +1;
    }
    return -1;
}