#include <iostream>
#include <fstream>

using namespace std;

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

int n,mid,i,x,e,a[100010],m,st,dr;

int rez0(int x)
{
    int sol;
    dr=n;
    st=1;
    while(st<=dr)
    {
        mid=(dr+st)/2;
        if(a[mid]<=x)
        {
            st=mid+1;
        }
        else
        {
            dr=mid-1;
        }
    }
    mid=(st+dr)/2;
    if(a[mid]>x)
        mid--;
    if(a[mid]==x)
        return mid;
    return -1;
}

int rez1(int x)
{
    int sol;
    dr=n;
    st=1;
    while(st<dr)
    {
        mid=(dr+st)/2;
        if(a[mid]<=x)
        {
            st=mid+1;
        }
        else
        {
            dr=mid;
        }
    }

    mid=(st+dr)/2;
    if(a[m]>=x)
        mid--;
    return mid;
}

int rez2(int x)
{
    int sol;
    dr=n;
    st=1;
    while(st<dr)
    {
        mid=(dr+st)/2;
        if(a[mid]<x)
        {
            st=mid+1;
        }
        else
        {
            dr=mid;
        }
    }
    mid=(dr+st)/2;
    if(a[mid]<x)
        mid++;
    return mid;
}

int main()
{
    f>>n;
    for(i=1;i<=n;i++)
    {
        f>>a[i];
    }
    f>>m;
    for(i=1;i<=m;i++)
    {
        f>>e;
        f>>x;
        if(e==0)
            g<<rez0(x)<<"\n";
        if(e==1)
            g<<rez1(x)<<"\n";
        if(e==2)
            g<<rez2(x);
    }
    return 0;
}