#include <bits/stdc++.h>

using namespace std;

#define INPUT "cautbin.in"
#define OUTPUT "cautbin.out"

ifstream fin(INPUT);
ofstream fout(OUTPUT);

long long v[100005];
long long N, M, val;

long long binsearch (long long val)
{
    long long st = 1, dr = N, newindex=0, mij;
    while (st < dr)
    {
        mij = (st + dr) / 2;
        if (v[mij] < val) st = mij+1;
        else dr = mij;
    }
    if (v[st] == val)
    {
        newindex=st;
        while(v[newindex]==val)
            newindex++;
        return newindex-1;
    }
    else
        return -1;
}

long long lowb(long long val)
{
    long long st = 1, dr = N, newindex=0, mij;
    while (st < dr)
    {
        mij = (st + dr) / 2;
        if (v[mij] < val) st = mij+1;
        else dr = mij;
    }
    return st;
}


long long upb(long long val)
{
    long long st = 1, dr = N, newindex=0, mij;
    while (st < dr)
    {
        mij = (st + dr + 1) / 2;
        if (v[mij] <= val) st = mij;
        else dr = mij-1;
    }
    return dr;
}


int main()
{

    fin >> N;
    for (long long i = 1; i <= N; i++)
        fin >> v[i];
    fin >> M;

    for (long long q = 1; q <= M; q++)
    {
        long long prompt;
        fin >> prompt;
        if (prompt == 0)
        {
            fin >> val;
            fout << binsearch(val) << endl;
        }
        else if (prompt == 1)
        {
            fin >> val;
            fout << upb(val) << endl;
        }
        else
        {
            fin >> val;
            fout <<  lowb(val) << endl;
        }
    }
    return 0;
}