#include <stdio.h>
#define nmax 100010
using namespace std;
int n,i,t[nmax],m,tip,x;
int cauta1(int st,int dr,int x)
{
    int m,sol=-1;
    while (st<=dr) {
        m=(st+dr)/2;
        if (t[m]==x) {
            sol=m; st=m+1;
        } else dr=m-1;
    }
    return sol;
}
int cauta2(int st,int dr,int x)
{
    int m;
    while (st<=dr) {
        m=(st+dr)/2;
        if (t[m]<=x) st=m+1; else
            dr=m-1;
    }
    return st-1;
}
int cauta3(int st,int dr,int x)
{
    int m;
    while (st<=dr) {
        m=(st+dr)/2;
        if (t[m]>=x) dr=m-1; else
            st=m+1;
    }
    return dr+1;
}
int main() {
freopen("cautbin.in","r",stdin);
freopen("cautbin.out","w",stdout);
scanf("%d",&n);
for (i=1;i<=n;i++) scanf("%d",&t[i]);
scanf("%d",&m);
for (i=1;i<=m;i++) {
    scanf("%d %d",&tip,&x);
    if (tip==0) printf("%d\n",cauta1(1,n,x)); else
    if (tip==1) printf("%d\n",cauta2(1,n,x)); else
    if (tip==2) printf("%d\n",cauta3(1,n,x));
}
return 0;
}