#include <iostream>
#include <fstream>
#define Nmax 100001
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

int n,v[Nmax];
int BinSearch0(int x)
{
    int l=1,r=n,sol=-1,m;
    while(l<=r)
    {
         m=(l+r)/2;
        if(x==v[m])
        {
            if(m>sol)  sol=m;
            l=m+1;
        }
        else
            if(x<v[m])
                r=m-1;
            else l=m+1;
    }
    return sol;
}

int BinSearch1(int x)
{
    int l=1,r=n,sol,m=-1;
    while(l<=r)
    {
         m=(l+r)/2;
        if(v[m]<=x)
        {
            sol=m;
            l=m+1;
        }
        else
             r=m-1;
    }
    return sol;
}

int BinSearch2(int x)
{
    int l=1,r=n,sol,m=-1;
    while(l<=r)
    {
         m=(l+r)/2;
        if(v[m]>=x)
        {
            sol=m;
            r=m-1;
        }
        else
             l=m+1;
    }
    return sol;
}
int main()
{
    int i,m,op,val;
    fin>>n;
    for(i=1;i<=n;i++)
        fin>>v[i];
    fin>>m;
   for(i=1;i<=m;i++)
   {
        fin>>op>>val;

        if(op==0)
            fout<<BinSearch0(val)<<"\n";
        if(op==1)
             fout<<BinSearch1(val)<<"\n";
        if(op==2)
             fout<<BinSearch2(val)<<"\n";
   }

    return 0;
}