#include <fstream>
#include <iostream>

using namespace std;

ifstream in("cautbin.in");
ofstream out("cautbin.out");
int q,s,cautat,a[100001],x,n,t,y,m;

int cautbin0()
{
//    int abc = 0;
    q=1;
    s=n;
    while(q<=s)
    {
//        abc++;
        cautat=(s+q)/2;
        if(a[cautat]<=x) q=cautat+1;
        else s=cautat-1;
    }
//    cout << abc << endl;
    if(a[s]==x) return s;
    return -1;
}
int cautbin1()
{
//    int abc = 0;
    q=1;
    s=n;
    while(q<=s)
    {
//        abc++;
        cautat=(s+q)/2;
        if(a[cautat]<=x) q=cautat+1;
        else s=cautat-1;
    }
//    cout << abc << endl;
    return s;
}
int cautbin2()
{
//    int abc = 0;
    q=1;
    s=n;
    while(q<=s)
    {
//        abc++;
        cautat=(s+q)/2;
        if(a[cautat]>=x) s=cautat-1;
        else q=cautat+1;
    }
//    cout << abc << endl;
    return q;
}

int main()
{
    in>>n;
    for(int i=1; i<=n; i++)
        in>>a[i];
    in>>m;
    for(int i=1; i<=m; i++)
    {
        in>>y>>x;
        if(y==0) out<<cautbin0()<<'\n';
        if(y==1) out<<cautbin1()<<'\n';
        if(y==2) out<<cautbin2()<<'\n';
    }
    return 0;
}