#include<fstream>
#define nx 100007
using namespace std;
int v[nx],n,m,i,q,x;

ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

int binary_search_0(int left, int right,int val)
{
    int mid;
    while(left<=right)
    {
        mid=(left+right)>>1;
        if(v[mid]<=val)left=mid+1;
        else right=mid-1;
    }

    if(v[mid]>val)mid--;
    if(v[mid]==val)return mid;
    return -1;
}

int binary_search_1(int left,int right,int val)
{
    int mid;
    while(left<=right)
    {
        mid=(left+right)>>1;
        if(v[mid]<=val)left=mid+1;
        else right=mid-1;
    }

    if(v[mid]>val)mid--;
    return mid;
}

int binary_search_2(int left, int right,int val)
{
    int mid;
    while(left<=right)
    {
        mid=(left+right)>>1;
        if(v[mid]<val)left=mid+1;
        else right=mid-1;
    }

    if(v[mid]<val)mid++;
    return mid;
}

int main()
{
    fin>>n;
    for(i=1;i<=n;i++)
        fin>>v[i];

    fin>>m;
    for(i=1;i<=m;i++)
    {
        fin>>q>>x;
        if(q==0)
            fout<<binary_search_0(1,n,x)<<"\n";
        if(q==1)
            fout<<binary_search_1(1,n,x)<<"\n";
        if(q==2)
            fout<<binary_search_2(1,n,x)<<"\n";
    }

    return 0;
}