#include <iostream>
#include <fstream>
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int bin1(int s,int d,int* x,int val)
{
    if(s<=d)
    {
        for(int t=d;t>=s;t--)
            if(val==x[t])
            return t;
        return -1;
    }
    int mid=(s+d)/2;
    if(x[mid]<=val)
        return bin1(mid,d,x,val);
    return bin1(s,mid-1,x,val);
}
int bin2(int s,int d,int* x,int val)
{
    if(s<=d)
    {
        for(int t=d;t>=s;t--)
            if(val>=x[t])
            return t;
    }
    int mid=(s+d)/2;
    if(x[mid]<=val)
        return bin2(mid,d,x,val);
    else
        return bin2(s,mid-1,x,val);
}
int bin3(int s,int d,int* x,int val)
{
    if(s<=d)
    {
        for(int t=s;t<=d;t++)
            if(x[t]>=val)
            return t;
    }
    int mid=(s+d)/2;
    if(x[mid]>=val)
        return bin3(mid,d,x,val);
    else
        return bin3(s,mid-1,x,val);
}
int i,j,n,poz,k;
int main()
{
    int tip1,val1;
    f>>n;
    int* v=new int[n+5];
    for(i=1;i<=n;i++)
        f>>v[i];
    f>>k;
    for(i=1;i<=k;i++)
    {
        f>>tip1>>val1;
        if(tip1==0)
            g<<bin1(1,n,v,val1)<<'\n';
        else
            if(tip1==1)
            g<<bin2(1,n,v,val1)<<'\n';
            else
                if(tip1==2)
                g<<bin3(1,n,v,val1)<<'\n';
    }
}