#include <fstream>

using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int n,m,c,x,i;
int v[100001];
int cbin0(int x);
int cbin1(int x);
int cbin2(int x);
int main()
{
    fin>>n;
    for(i=0;i<n;i++)
        fin>>v[i];
    fin>>m;
    for(i=0;i<m;i++)
    {
        fin>>c>>x;
        if(c==0)
            fout<<cbin0(x)<<'\n';
        if(c==1)
            fout<<cbin1(x)<<'\n';
        if(c==2)
            fout<<cbin2(x)<<'\n';
    }
    return 0;
}
int cbin0(int x)
{
    int st,dr,mij;
    st=0;
    dr=n-1;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(v[mij]<x)
            st=mij+1;
        else if(v[mij]>x)
            dr=mij-1;
        else if(v[mij]==x)
        {
            while(v[mij+1]==x)
                mij++;
            return mij+1;
        }
    }
    return -1;
}
int cbin1(int x)
{
    int st,dr,mij;
    st=0;
    dr=n-1;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(v[mij]<x)
            st=mij+1;
        else if(v[mij]>x)
            dr=mij-1;
        else if(v[mij]==x)
        {
            while(v[mij+1]==x)
                mij++;
            return mij+1;
        }
    }
    while(v[st]>x)
        st--;
    return st+1;
}
int cbin2(int x)
{
    int st,dr,mij;
    st=0;
    dr=n-1;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(v[mij]<x)
            st=mij+1;
        else if(v[mij]>x)
            dr=mij-1;
        else if(v[mij]==x)
        {
            while(v[mij-1]==x)
                mij--;
            return mij+1;
        }
    }
    while(v[st]<x)
        st++;
    return st+1;
}