#include <fstream>
using namespace std;
ifstream cin ("cautbin.in");
ofstream cout ("cautbin.out");
int v[100001],vi[100001],vf[100001],w[100001],n;

int cb0(int x)
{
    int st=1,dr=n,mj;
    while (st<=dr)
    {
        mj=(st+dr)/2;
        if (v[mj]==x)
            return vf[mj];
        else if (v[mj]<x)
            st=mj+1;
        else
            dr=mj-1;
    }
    return -1;
}

int cb1(int x)
{
    int st=1,dr=n,mj,i;
    while (st<=dr)
    {
        mj=(st+dr)/2;
        if (v[mj]==x)
            return vf[mj];
        else if (v[mj]<x)
        {
            st=mj+1;
            if (v[st]>x)
                return vf[mj];
        }
        else
        {
            dr=mj-1;
            if (v[dr]<=x)
                return vf[dr];
        }
    }
}

int cb2(int x)
{
    int st=1,dr=n,mj,i;
    while (st<=dr)
    {
        mj=(st+dr)/2;
        if (v[mj]==x)
            return vi[mj];
        else if (v[mj]<x)
        {
            st=mj+1;
            if (v[st]>=x)
                return vi[mj];
        }
        else
        {
            dr=mj-1;
            if (v[dr]<x)
                return vi[mj];
        }
    }
}

int main()
{
    int i,m,q,x,poz;
    cin>>n;
    for (i=1;i<=n;i++)
    {
        cin>>x;
        w[x]++;
    }
    poz=0; n=0;
    for (i=1;i<=100000;i++)
    {
        if (w[i])
        {
            n++;
            v[n]=i;
            vi[n]=poz+1;
            vf[n]=vi[n]+w[i]-1;
            poz=vf[n];
        }
    }
    cin>>m;
    for (i=1;i<=m;i++)
    {
        cin>>q>>x;
        if (q==0)
            cout<<cb0(x)<<"\n";
        if (q==1)
            cout<<cb1(x)<<"\n";
        if (q==2)
            cout<<cb2(x)<<"\n";
    }
}