#include <iostream>
#include <fstream>
#define N 100010

using namespace std;

ifstream f("cautbin.in");
ofstream g("cautbin.out");
int max1=-1,min1;
int v[N],i,j,x,y,t,r,n,k;
void caut1(int s,int d,int x)
{
    if(s<d)
    {
    int m;
    m=(s+d)/2;
    if(v[m]==x)
    {
        if(max1<m)
            max1=m;
    }
        if(v[m]>x)
            caut1(s,m,x);
        else
        if(v[m]<=x)
            caut1(m+1,d,x);
    }
}
void caut2(int s,int d,int x)
{
    if(s<d)
    {
    int m;
    m=(s+d)/2;
    if(v[m]<=x)
    {
        if(m>max1)
            max1=m;
    }
        if(v[m]>x)
            caut2(s,m,x);
        else
        if(v[m]<=x)
            caut2(m+1,d,x);
    }
}
void caut3(int s,int d,int x)
{
    if(s<d)
    {
    int m;
    m=(s+d)/2;
    if(v[m]>=x)
    {
        if(m<min1)
        min1=m;
    }
        if(v[m]>=x)
            caut3(s,m,x);
        else
            if(v[m]<x)
            caut3(m+1,d,x);
    }
}
int main()
{
    f>>n;
    for(i=1;i<=n;i++)
        f>>v[i];
    f>>k;
    while(k!=0)
    {
        f>>y>>x;
        max1=-1;
        min1=n;
        if(y==0)
        {
            caut1(1,n,x);
            g<<max1<<endl;
        }
        else
            if(y==1)
            {
                caut2(1,n,x);
                g<<max1<<endl;
            }
            else
                if(y==2)
                {
                    caut3(1,n,x);
                    g<<min1<<endl;
                }
        k--;
    }
}