#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 p=0,i;
    for(i=1<<20;i>=1;i=i>>1)
        if(p+i<=l && v[p+i]<=x)
            p+=i;
    while(v[p]>x)
        p--;
    return p;
}

int cbin2(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;
    while(v[p]==x)
        p--;
    while(v[p]<x)
        p++;
    return p;
}

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;
}