#include <fstream>
using namespace std;
ifstream cin("cautbin.in");
ofstream cout("cautbin.out");
int n, a[100001], m;
int cautare0(int x);
int cautare1(int x);
int cautare2(int x);
int main()
{
    cin >> n;

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

    cin >> m;

    int t, x;
    for(int i = 1; i <= m; i++)
    {
        cin >> t >> x;

        if(t == 0)
            cout << cautare0(x) << '\n';
        else if(t == 1)
            cout << cautare1(x) << '\n';
        else if(t == 2)
            cout << cautare2(x) << '\n';

    }

    return 0;
}

int cautare0(int x)
{
    int poz = 0, pw = 1;

    while((pw << 1) <= n)
        pw <<= 1;

    while(pw)
    {
        if(poz + pw <= n)
            if(a[poz + pw] <= x)
                poz += pw;

        pw /= 2;
    }

    if(a[poz] == x)
        return poz;
    else
        return -1;
}

int cautare1(int x)
{
    int poz = 0, pw = 1;

    while((pw << 1) <= n)
        pw <<= 1;

    while(pw)
    {
        if(poz + pw <= n)
            if(a[poz + pw] <= x)
                poz += pw;

        pw /= 2;
    }

    return poz;
}

int cautare2(int x)
{
    int poz = n + 1, pw = 1;

    while((pw << 1) <= n)
        pw <<= 1;

    while(pw)
    {
        if(poz - pw >= 1)
            if(a[poz - pw] >= x)
                poz -= pw;

        pw /= 2;
    }

    return poz;
}