#include <iostream>
#include <fstream>

using namespace std;

ifstream fi("cautbin.in");
ofstream fo("cautbin.out");

long int a[100050];
long int n,M;

void cit(long int i)
{
    if(i<=n)
        {fi>>a[i];
        cit(i+1);}
}


long int bin0(long int left, long int right, long int x)
{
    long int m;

    while(left<=right)
    {
        m=(left+right)/2;

        if(a[m]<=x)
            left  =m+1;
        else
            right =m-1;
    }

    m=(left+right)/2;

    if(a[m] > x)
        m--;

    if(a[m]==x)
        return m;
    else
        return -1;
}


long int bin1(long int left, long int right, long int x)
{
    long int m;

    while(left < right)
    {
        m=(left+right)/2;

        if(a[m]<=x)
            left=m+1;
        else
            right=m;
    }

    m=(left+right)/2;

    if(a[m] >x)
        m--;

    return m;
}


long int bin2(long int left, long int right, long int x)
{
    long int m;

    while(left < right)
    {
        long int m=(left+right)/2;

        if(a[m] < x)
            left=m+1;
        else
            right=m;
    }

    m=(left+right)/2;

    if(a[m]<x)
        m++;

    return m;
}

int main()
{
    fi>>n;

    cit(1);

    fi>>M;

    for(long int i=0;i<M;i++)
    {
        long int x,y;

        fi>>x>>y;

        if(x==0)
            fo<<bin0(0,n-1,y)<<'\n';
        if(x==1)
            fo<<bin1(0,n-1,y)<<'\n';
        if(x==2)
            fo<<bin2(0,n-1,y)<<'\n';
    }

    return 0;
}