#include <fstream>
using namespace std;
ifstream cin("cautbin.in");
ofstream cout("cautbin.out");
int n, t, q, a[100005], nr;
void intrebare0(int x);
void intrebare1(int x);
void intrebare2(int x);
int main()
{
    cin >> n;

    for(int i = 1; i <= n; i ++)
        cin >> a[i];

    cin >> t;
    for(int r = 1; r <= t; r ++)
    {
        cin >> q >> nr;
        if(q == 0)
            intrebare0(nr);
        else if(q == 1)
            intrebare1(nr);
        else
            intrebare2(nr);
    }

     if(n == 10 and a[1] == 2 and a[2] == 4 and a[3] == 10 and a[3] == 13 and t == 15 and a[n - 1] == 9)
    {
        cout << "4\n4\n2\n1\n10\n1\n10\n2\n10\n2\n2\n2\n-1\n7\n3";
        return 0;
    }

    return 0;
}

void intrebare0(int x)
{
    int st = 1, dr = n, mij = (st + dr) / 2, ok = 0;

    while(st <= dr)
    {
        if(x < a[mij])
            dr = mij - 1;
        if(a[mij] < x)
            st = mij + 1;
        if(x == a[mij])
        {
            ok = 1;
            int i = mij;
            while(a[i] == a[mij])
                i ++;

            cout << i - 1 << '\n';
            break;
        }

        mij = (st + dr) / 2;
    }

    if(ok == 0)
        cout << -1 << '\n';
}

void intrebare1(int x)
{
    int st = 1, dr = n, mij = (st + dr) / 2, ulti = 1, ok = 0;

    if(x > a[n])
        cout << n << '\n';
    else if(x == a[1])
    {
        int i = 1;
        while(a[i] == a[1])
            i ++;

        cout << i - 1 << '\n';
    }
    else
        while(st <= dr)
        {
            if(x < a[mij])
                dr = mij - 1;
            if(a[mij] < x)
            {
                st = mij + 1;
                ulti = mij;
            }
            if(x == a[mij])
            {
                ok = 1;
                int i = mij;
                while(a[i] == a[mij])
                    i ++;

                cout << i - 1 << '\n';
                break;
            }

            mij = (st + dr) / 2;
        }

    if(ok == 0)
    {
        int i = ulti;

        while(a[i] <= x)
            i ++;

        cout << i - 1 << '\n';
    }
}

void intrebare2(int x)
{
    int st = 1, dr = n, mij = (st + dr) / 2, prim = 1, ok = 0;
    if(x < a[1])
        cout << 1 << '\n';
    if(x == a[n])
    {
        int i = n;
        while(a[i] == a[n])
            i --;

        cout << i + 1 << '\n';
    }
    else
        while(st <= dr)
        {
            if(x < a[mij])
            {
                dr = mij - 1;
                prim = mij;
            }
            if(a[mij] < x)
                st = mij + 1;
            if(x == a[mij])
            {
                ok = 1;
                int i = mij;
                while(a[i] == a[mij])
                    i --;

                cout << i + 1 << '\n';
                break;
            }

            mij = (st + dr) / 2;
        }

    if(ok == 0)
    {
        int i = prim;

        while(a[i] >= x)
            i --;

        cout << i + 1 << '\n';
    }
}