#include <bits/stdc++.h>

using namespace std;

ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

int n,m,v[100005],x,nr;

int cb(int a)
{
    int l=1,r=n,m,rez=-1;
    while(l<=r)
    {
        m=(l+r)/2;
        if(v[m]==a)
            rez=m;
        if(v[m]<=a)
            l=m+1;
        if(v[m]>a)
            r=m-1;
    }
    return rez;
}

int cbmax(int a)
{
    int l=1,r=n,m,rez;
    while(l<=r)
    {
        m=(l+r)/2;
        if(v[m]<=a)
            rez=m,l=m+1;
        if(v[m]>a)
            r=m-1;
    }
    return rez;
}

int cbmin(int a)
{
    int l=1,r=n,rez,m;
    while(l<=r)
    {
        m=(l+r)/2;
        if(v[m]>=a)
            rez=m,r=m-1;
        if(v[m]<a)
            l=m+1;
    }
    return rez;
}

int main()
{
    fin>>n;
    for(int i=1;i<=n;++i)
        fin>>v[i];
    fin>>m;
    for(int i=1;i<=m;++i)
    {
        fin>>x>>nr;
        if(x==0)
            fout<<cb(nr)<<'\n';
        else if(x==1)
            fout<<cbmax(nr)<<'\n';
        else if(x==2)
            fout<<cbmin(nr)<<'\n';
    }
    return 0;
}