#include <fstream>
using namespace std;

ifstream in ("cautbin.in");
ofstream out ("cautbin.out");
int cerinta[100001], v[100001];
int cautbinara (int p, int u, int k) {
    int m;

    while (p <= u) {
        m = (p + u) / 2;
        if (v[m] <= k)
            p = m + 1;
        else
            u = m - 1;
    }
    m = (p + u) / 2;

    if (v[m] > k) m--;
    if (v[m] == k)
        return m;
    return -1;
}

int functie2 (int p, int u, int k) {
    int m, n = u;

    while (p < u){
        m = (p + u) / 2;
        if (v[m] <= k)
            p = m + 1;
        else
            u = m;
    }

    m = (p + u) / 2;
    if (v[m] > k)
       -- m;
    return m;
}
int functie3(int p, int u, int k)
{
     int m;

    while (p < u) {
        m = (p + u) / 2;
        if (v[m] < k)
            p = m + 1;
        else
            u = m;
    }

    m = (p + u) / 2;
    if (v[m] < k)
       ++ m;
    return m;
}
int main()
{
     int n, i , m,mij,st,dr,x,s;
     in>>n;
     for(i=1;i<=n;i++)
        in>>v[i];
     in>>m;
     for(i=1;i<=m;i++)
     {
         in>>x>>s;
         if(x==0)
         {
             out<<cautbinara(1,n,s)<<'\n';
         }
         if(x==1)
         {
            out<<functie2(1,n,s)<<'\n';
         }
         if(x==2)
         {
             out<<functie3(1,n,s)<<'\n';
         }
     }
     return 0;
}