#include <bits/stdc++.h>

using namespace std;

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

int v[100001];

int cbin0(int x,int l)
{
    v[0]=-1;
    int p=0,i;
    for(i=1<<20;i>=1;i=i>>1)
        if(p+i<=l && v[p+i]<=x)
            p+=i;
    if(v[p]==x)
        return p;
    else
        return -1;
}

int cbin1(int x,int l)
{
    v[0]=-1;
    int pos=0,i;
    for(i=1<<20;i>=1;i=i>>1)
        if(pos+i<=l && v[pos+i]<=x)
            pos+=i;
    while(v[pos]>x)
        pos--;
    return pos;
}

int cbin2(int x,int l)
{
    v[0]=-1;
    int pos=0,i;
    for(i=1<<20;i>=1;i=i>>1)
        if(pos+i<=l && v[pos+i]<=x)
            pos+=i;
    while(v[pos]==x)
        pos--;
    while(v[pos]<x)
        pos++;
    return pos;
}

int main()
{
    int n,m,i,a,x;
    fin>>n;
    for(i=1;i<=n;i++)
        fin>>v[i];
    sort(v+1,v+n+1);
    fin>>m;
    while(m--)
    {
        fin>>a>>x;
        if(a==0)
            fout<<cbin0(x,n)<<'\n';
        else if(a==1)
            fout<<cbin1(x,n)<<'\n';
        else
            fout<<cbin2(x,n)<<'\n';
    }
    return 0;
}