#include <iostream>
#include <fstream>


using namespace std;

int v[100100];
ifstream in("cautbin.in");
ofstream out("cautbin.out");
int caut(int st,int dr,int x)
{
    int mij;
    while(st<=dr)
    {
        mij=st+(dr-st)/2;
        if(v[mij]<=x)
              st=mij+1;
              else dr=mij-1;
    }
    mij=st+(dr-st)/2;
    if(v[mij]>x)mij--;
    if(v[mij]==x)return mij;
    return -1;
}

int lower_bin(int st, int dr, int x)
{
    int mij=st+(dr-st)/2;
    while(st<dr)
    {
        mij=st+(dr-st)/2;
        if(v[mij]>=x)dr=mij;
        else st=mij+1;

    }
    mij=st+(dr-st)/2;
     if(v[mij]>x)mij--;
    return mij;
}

int upper_bin(int st, int dr, int x)
{

    int mij=st+(dr-st)/2;
    while(st<dr)
    {
        mij=st+(dr-st)/2;
        if(v[mij]<x)st=mij+1;
         else dr=mij;

    }
   mij=st+(dr-st)/2;

     if(v[mij]<x)mij++;
    return mij;
}

int main()
{
    int n;
    int op,arg;
    in>>n;
    for(int i=1; i<=n; i++)in>>v[i];
    int nrop;
    in>>nrop;
    for(int i=1; i<=nrop; i++)
    {
        in>>op>>arg;
        switch(op)
        {
        case 0:
        {
            out<<caut(1,n,arg);
            break;
        }
        case 1:
        {
            out<<lower_bin(1,n,arg);
            break;
        }
        case 2:
        {
            out<<upper_bin(1,n,arg);
            break;
        }

        }

        out<<'\n';
    }

    return 0;
}