#include<fstream>
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int n,v[100001];

void bin_0(int st,int dr,int x)
{
    int j,mij,gasit=0;;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(v[mij]==x)
        {
            j=mij+1;
            while(v[j]==x) j++;
            g<<j-1<<'\n'; gasit=1; break;
        }
        else if(v[mij]>x) dr=mij-1;
             else st=mij+1;
    }
    if(!gasit) g<<-1<<'\n';
}

void bin_1(int st,int dr,int x)
{
    int j,mij;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(v[mij]<=x)
        {
            j=mij+1;
            while(v[j]<=x && j<=n) j++;
            g<<j-1<<'\n'; break;
        }
        else dr=mij-1;
    }
}

void bin_2(int st,int dr,int x)
{
    int j,mij;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(v[mij]>=x)
        {
            j=mij-1;
            while(v[j]>=x && j>0) j--;
            g<<j+1<<'\n'; break;
        }
        else st=mij+1;
    }
}

int main()
{
    int i,m,q,x;
    f>>n;
    for(i=1;i<=n;i++)
        f>>v[i];
    f>>m;
    for(i=1;i<=m;i++)
    {
        f>>q>>x;
        if(q==0) bin_0(1,n,x);
        else if(q==1) bin_1(1,n,x);
             else bin_2(1,n,x);
    }
    f.close();
    g.close();
    return 0;
}