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

int n, m, v[100002];

ifstream f ("cautbin.in");
ofstream g ("cautbin.out");

int cautbin0(int nr)
{
    long long int mid;
    int st=1, dr=n;
    while(st<dr)
    {
        mid=(st+dr)/2;
        if((v[mid]==nr) && (v[mid+1]!=nr))
            return mid;
        if(v[mid]<=nr)
            st=mid+1;
        else
            dr=mid;
    }
    if(v[st]==nr)
        return st;
    return -1;
}

int cautbin1(int nr)
{
    long long int mid;
    int st=1, dr=n;
    while(st<dr)
    {
        mid=(st+dr)/2;
        if(v[mid]<=nr)
            st=mid+1;
        else
            dr=mid;
    }
    if (v[st]>nr)
        --st;
    return st;
}

int cautbin2(int nr)
{
    long long int mid;
    int st=1, dr=n;
    while(st<dr)
    {
        mid=(st+dr)/2;
        if(v[mid]>=nr)
            dr=mid;
        else
            st=mid+1;
    }
    if (v[mid]<nr)
        ++ mid;
    return mid;
}

int main ()
{
    int c, nr, i;
    f>>n;
    for(i=1; i<=n; i++)
        f>>v[i];
    f>>m;
    for(i=0; i<m; i++)
    {
        f>>c>>nr;
        if(!c)
            g<<cautbin0(nr)<<"\n";
        else if(c==1)
            g<<cautbin1(nr)<<"\n";
        else
            g<<cautbin2(nr)<<"\n";
    }
    f.close();
    g.close();
    return 0;
}