#include <fstream>

using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int n,a[100005],m,i,x,p,sol;
int cerinta_1(int x)
{
    int stg=1,dr=n;
    int mij;
    while(stg<=dr)
    {
        mij=(stg+dr)/2;
        if(a[mij]==x)
            break;
        else
            if(a[mij]>x)
                dr=mij-1;
        else
            if(a[mij]<x)
                stg=mij+1;
    }
    if(a[mij]==x)
    {
        while(a[mij]==x)
            mij++;
        return mij-1;
    }
    else
        return -1;
}
int cerinta_2(int x)
{
    int stg=1,dr=n;
    int mij;
    while(stg<=dr)
    {
        mij=(stg+dr)/2;
        if(a[mij]==x)
            break;
        else
            if(a[mij]>x)
                dr=mij-1;
        else
            if(a[mij]<x)
                stg=mij+1;
    }
    if(a[mij]==x||a[mij]<x)
    {
        while((a[mij]==x||a[mij]<x)&&mij<=n)
            mij++;
        return mij-1;
    }
    else
    {
        while(a[mij]>x&&mij>0)
            mij--;
        return mij;
    }
}
int cerinta_3(int x)
{
    int stg=1,dr=n;
    int mij;
    while(stg<=dr)
    {
        mij=(stg+dr)/2;
        if(a[mij]==x)
            break;
        else
            if(a[mij]>x)
                dr=mij-1;
        else
            if(a[mij]<x)
                stg=mij+1;
    }
    if(a[mij]==x||a[mij]>x)
    {
        while((a[mij]==x||a[mij]>x)&&mij>0)
            mij--;
        return mij+1;
    }
    else
    {
        while((a[mij]<x)&&mij<n)
            mij++;
        return mij;
    }
}
int main()
{
    fin>>n;
    for(i=1;i<=n;i++)
        fin>>a[i];
    fin>>m;
    for(i=1;i<=m;i++)
    {
        fin>>p>>x;
        if(p==0)
            sol=cerinta_1(x);
        if(p==1)
            sol=cerinta_2(x);
        if(p==2)
            sol=cerinta_3(x);
        fout<<sol<<"\n";
    }
    return 0;
}