#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

typedef long long ll;

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

vector<int> v;


int cautBinar0(int x)
{
    ll mij,st=0,dr=v.size()-1,found=0;
    mij=st+(dr-st)/2;
    while(st<=dr&&found==0)
    {
        mij=st+(dr-st)/2;
        if(v[mij]==x)
            found=1;
        else if(v[mij]<x)
            st=mij+1;
        else if(v[mij]>x)
            dr=mij-1;
    }
    if(found==0)
        return -1;
    else
    {
        while(mij<v.size()&&v[mij]==x)
            mij++;
        return mij;
    }
}

int cautBinar1(int x)
{
    ll mij,st=0,dr=v.size()-1,found=0;
    mij=st+(dr-st)/2;
    while(st<=dr&&found==0)
    {
        mij=st+(dr-st)/2;
        if(v[mij]==x)
            found=1;
        else if(v[mij]<x)
            st=mij+1;
        else if(v[mij]>x)
            dr=mij-1;
    }
    while(mij<v.size()&&v[mij]<=x)
        mij++;
    return mij;
}

int cautBinar2(int x)
{
    ll mij,st=0,dr=v.size()-1,found=0;
    mij=st+(dr-st)/2;
    while(st<=dr&&found==0)
    {
        mij=st+(dr-st)/2;
        if(v[mij]==x)
            found=1;
        else if(v[mij]<x)
            st=mij+1;
        else if(v[mij]>x)
            dr=mij-1;
    }
    if(found==1)
    {
        while(mij>=0&&v[mij]>=x)
            mij--;
        return mij+2;
    }
    if(v[mij]<x)
        mij++;
    return min((ll)v.size(),mij+1);
}

int main()
{
    int n,m;
    fin>>n;
    for(int i=0;i<n;i++)
    {
        int x;
        fin>>x;
        v.push_back(x);
    }
    fin>>m;
    for(int i=0;i<m;i++)
    {
        int c,x;
        fin>>c>>x;
        switch (c)
        {
            case 0: fout<<cautBinar0(x)<<"\n";
                    break;
            case 1: fout<<cautBinar1(x)<<"\n";
                    break;
            case 2: fout<<cautBinar2(x)<<"\n";
        }
    }

    return 0;
}