#include <bits/stdc++.h>

#define LMax 100005
#define INfile "cautbin.in"
#define OUTfile "cautbin.out"

using namespace std;

ifstream fin(INfile);
ofstream fout(OUTfile);

int m, n, v[LMax], x, y;

int cb1(int st, int dr, int nr)
{
    int mid;
    while (st <= dr)
    {
        mid = st + (dr - st) / 2;
        if (v[mid] > nr)
            dr = mid - 1;
        else if (v[mid] < nr)
            st = mid + 1;
        if (v[mid] == nr && v[mid + 1] != v[mid])
            return mid;
        else if (v[mid] == nr)
            st = mid + 1;
    }
    return -1;
}

int cb2(int st, int dr, int nr)
{
    int mid;
    while (st <= dr)
    {
        mid = st + (dr - st) / 2;
        if (v[mid] > nr)
            dr = mid - 1;
        else if (v[mid] < nr)
            st = mid + 1;
        if (v[mid] == nr && v[mid + 1] != v[mid])
            return mid;
        else if (v[mid] == nr)
            st =  mid + 1;
    }
    m=(st+dr)/2;
    if(v[mid]>nr)
        --m;
    return mid;
}

int cb3(int st, int dr, int nr)
{
int mid;
    while (st <= dr)
    {
        mid = st + (dr - st) / 2;
        if (v[mid] > nr)
            dr = mid - 1;
        else if (v[mid] < nr)
            st = mid + 1;
        if (v[mid] == nr && v[mid - 1] != v[mid])
            return mid;
        else if (v[mid] == nr)
            dr =  mid - 1;
    }
    m=(st+dr)/2;
    if(v[mid]<nr)
        ++m;
        return mid;
}

int main()
{
    fin >> n;
    for (int i = 1; i <= n; ++i)
        fin >> v[i];
    fin >> m;
    for (int i = 1; i <= m; ++i)
    {
        fin >> x >> y;
        if (x == 0)
            fout<<cb1(1, n, y)<<'\n';
        else if (x == 1)
            fout<<cb2(1, n, y)<<'\n';
        else if (x == 2)
            fout<<cb3(1, n, y)<<'\n';
    }
    return 0;
}