#include <cstdio>
using namespace std;

int n,m,a[100002];

int cautbin1(int x)
{
    int st=1,dr=n,mij;
    while(st<dr)
    {
        mij=st+(dr-st)/2;
        if(a[mij]==x)
        {
            while(a[mij+1]==x&&mij+1<=n) ++mij;
            return mij;
        }
        else if(x<a[mij]) dr=mij-1;
             else st=mij+1;
    }
    return -1;
}

int cautbin2(int x)
{
    int st=1,dr=n,mij;
    while(st<dr)
    {
        mij=st+(dr-st)/2;
        if(a[mij]<=x) st=mij+1;
        else dr=mij;
    }
    if(a[st]>x) --st;
    return st;
}

int cautbin3(int x)
{
    int st=1,dr=n,mij;
    while(st<dr)
    {
        mij=st+(dr-st)/2;
        if(a[mij]<x) st=mij+1;
        else dr=mij;
    }
    if(a[st]<x) ++st;
    return st;
}

int main()
{
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);
    int i,t,x;
    scanf("%d",&n);
    for(i=1;i<=n;++i) scanf("%d",&a[i]);
    scanf("%d",&m);
    while(m)
    {
        --m;
        scanf("%d%d",&t,&x);
        switch(t)
        {
            case 0: printf("%d\n",cautbin1(x)); break;
            case 1: printf("%d\n",cautbin2(x)); break;
            case 2: printf("%d\n",cautbin3(x)); break;
        }
    }
    return 0;
}