#include <bits/stdc++.h>
using namespace std;
ifstream in("cautbin.in");
ofstream out("cautbin.out");
int v[100005], n;
int cb0(int x)
{
    int m, st = 1, dr = n;
    while(st <= dr)
    {
        m = (st + dr) / 2;
        if(v[m] <= x)
        {
            st = m + 1;
        }
        else
            dr = m - 1;
    }
    if(v[dr] != x)
        return -1;

    else

        return dr;
}
int cb1(int x)
{
    int m, st = 1, dr = n;
    while(st <= dr)
    {
        m = (st + dr) / 2;
        if(v[m] <= x)
        {
            st = m + 1;
        }
        else
            dr = m - 1;

    }
    return dr;
}
int cb2(int x)
{
    int m, st = 1, dr = n;
    while(st <= dr)
    {
        m = (st + dr) / 2;
        if(v[m] >= x)
        {
            dr = m - 1;
        }
        else
            st = m + 1;
    }
    return st;
}
int main()
{
     int x;
     int var;
     int m;
     in >> n;
     for(int i = 1; i <= n; i++)
     {
         in >> v[i];
     }
     in >> m;
     for(int i = 1; i <= m; i++)
     {
         in >> var >> x;
         if(var == 0)
            out << cb0(x) << '\n';
         if(var == 1)
            out << cb1(x) << '\n';
         if(var == 2)
            out << cb2(x) << '\n';
     }
    return 0;
}