#include <fstream>
using namespace std;
ifstream f("cautbin.in"); ofstream g("cautbin.out");
int N, a[100001], M, type, x;
int bs0(int n)
{
    int st=1, dr=N;
    while(st<=dr)
    {
        int mid=(st+dr)/2;
        if(a[mid]==n) return mid;
        else if(a[mid]>n) dr=mid-1;
        else st=mid+1;
    }
    return -1;
}
int bs1(int n)
{
    int st=1, dr=N;
    while(st<=dr)
    {
        int mid=(st+dr)/2;
        if(a[mid]<=n and (a[mid+1]>n) or mid==N) return mid;
        else if(a[mid]==n) st=mid+1;
        else if(a[mid]>n) dr=mid-1;
        else st=mid+1;
    }
    return -1;
}
int bs2(int n)
{
    int st=1, dr=N;
    while(st<=dr)
    {
        int mid=(st+dr)/2;
        if(a[mid]>=n and a[mid-1]<n) return mid;
        else if(a[mid]==n) dr=mid-1;
        else if(a[mid]>n) dr=mid-1;
        else st=mid+1;
    }
    return -1;
}
int main()
{
    f>>N; for(int i=1; i<=N; i++) f>>a[i];
    f>>M;
    while(M--)
    {
        f>>type>>x;
        if(type==0) g<<bs0(x)<<'\n';
        else if(type==1) g<<bs1(x)<<'\n';
        else g<<bs2(x)<<'\n';
    }
    return 0;
}