#include <iostream>
#include <fstream>
using namespace std;

int cautbin0(int t[], int a, int b, int k)
{
    int c=(a+b)/2;
    if (a==b&&t[a]!=k) return -1;
    if (k==t[c])
    {
        while (k==t[c]) c++;
        return c-1;
    }
    else
    {
        if (k>t[c]) cautbin0(t, c+1, b, k);
        else cautbin0(t, a, c, k);
    }
}
int cautbin1(int t[], int a, int b, int k)
{
    int c=(a+b)/2;
    if (a==b&&t[a]!=k) return -1;
    if (k>=t[c])
    {
        while (k>=t[c]) c++;
        return c-1;
    }
    else
    {
        if (k>t[c]) cautbin1(t, c+1, b, k);
        else cautbin1(t, a, c, k);
    }
}
int cautbin2(int t[], int a, int b, int k)
{
    int c=(a+b)/2;
    if (a==b&&t[a]!=k) return -1;
    if (k>=t[c])
    {
        while (k<=t[c]) c--;
        return c+1;
    }
    else
    {
        if (k>t[c]) cautbin2(t, c+1, b, k);
        else cautbin2(t, a, c, k);
    }
}
int main()
{
    int n, m, k, szam;
    ifstream f("cautbin.in");
    ofstream g("cautbin.out");
    int t[100000];
    f>>n;
    for (int i=1; i<=n; i++)
    {
        f >> t[i];
    }
    f>>m;
    for (int i=1; i<=m; i++)
    {
        f>>szam>>k;
        if (szam==0) g << cautbin0(t, 1, n, k)<< " ";
        if (szam==1) g << cautbin1(t, 1, n, k)<< " ";
        if (szam==2) g << cautbin2(t, 1, n, k)<< " ";
    }
    f.close();
    g.close();
    return 0;
}