#include <iostream>
#include <fstream>
using namespace std;
ifstream f ("cautarebin.in");
ofstream g ("cautarebin.out");
int a[100005], b[100005][5];
void cautarebinara0(int l, int r, int y, int &p)
{
    int m;
    if(l<=r)
    {
        m=(l+r)/2;
        if(y==a[m])
            if(m>p) p=m;
        if(a[m-1]==y)cautarebinara0(1, m-1, y, p);
        if(a[m+1]==y)cautarebinara0(m+1, r, y, p);
    }
}
void cautarebinara1(int l, int r, int y, int &p)
{
    int m;
    if(l<=r)
    {
        m=(l+r)/2;
        if(a[m]<=y)
        {
            cautarebinara1(m+1, r, y, p);
            if(p<m) p=m;
        }
        else cautarebinara1(l, m-1, y, p);
    }
}
void cautarebinara2(int l, int r, int y, int &p)
{
    int m;
    if(l<=r)
    {
        m=(l+r)/2;
        if(a[m]>=y)
        {
            cautarebinara2(l, m-1, y, p);
            if(p>m) p=m;
        }
        else cautarebinara2(m+1, r, y, p);
    }
}
int main()
{
    int n, i, m, p, y, x;
    f>>n;
    for(i=1; i<=n; i++)
        f>>a[i];
    f>>m;
    for(i=1; i<=m; i++)
    {
        f>>x>>y;
        if(x==0)
        {
            p=0;
            cautarebinara0(1, n, y, p);
            g<<p<<"\n";
        }
        if(x==1)
        {
            p=0;
            cautarebinara1(1, n, y, p);
            g<<p<<"\n";
        }
        if(x==2)
        {
            p=n+1;
            cautarebinara2(1, n, y, p);
            g<<p<<"\n";
        }
    }
    return 0;
}