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

int a[100000];
int bin(int v[],int val, int n)
{
    int ans = 0, st = 1, dr = n, med = 0;
    while (st <= dr)
    {
        med = (st + dr)/2;
        if (v[med] <= val)
        {
           st = med + 1;
           ans = med;
        }
        else
           dr = med - 1;
    }
    return ans;
}

int binn(int v[],int val, int n)
{
    int ans = 0, st = 1, dr = n;
    while (st <= dr)
    {
        int med = (st + dr)/2;
        if (v[med] >= val)
        {
           dr = med - 1;
           ans = med;
        }
        else
           st = med + 1;
    }
    return ans;
}

int main()
{
    int n;
    fin >> n;
    for (int i = 1; i <= n; i++)
    {
        fin >> a[i];
    }
    int m, t0, t1, t2;
    fin >> m;
    for (int i = 1; i <= m; i++)
    {
        int task, x;
        fin >> task >> x;
        int poz = bin(a, x, n);
        if (a[poz] == x)
            t0 = poz;
        else
            t0 = -1;
        t1 = poz;
        t2 = binn(a, x, n);
        if (task == 0)
            fout << t0 << '\n';
        else if (task == 1)
                fout << t1 << '\n';
        else
            fout << t2 << '\n';
    }
    return 0;
}