#include <cstdio>
using namespace std;

int binKer_0(long a[], long x, int n)

{

    int bal=1, jobb=n, k;

    while(bal<=jobb){

        k=(bal+jobb)/2;

        if(x<a[k]) jobb=k-1;

        else if(x>a[k]) bal=k+1;

             else{

                int k2=k;

                while(a[k]==a[k2]){

                    k2++;

                }

                return k2-1;

             }

    }

    return -1;

}


int binKer_1(long a[], long x, int n)
{
    int bal=1, jobb=n;

    while(bal<jobb){
        int k = (bal+jobb+1)/2;

        if(a[k]>x) jobb = k-1;
        else bal = k;
    }

    return bal;
}

int binKer_2(long a[], long x, int n)
{
    int bal=1, jobb=n;

    while(bal<jobb){
        int k=(bal+jobb)/2;

        if(a[k]<x) bal = k+1;
        else jobb = k;
    }

    return bal;
}

int main()
{

    FILE *in = fopen("cautbin.in", "r");
    FILE *out = fopen("cautbin.out", "w");

    int n, m;
    long x, l;

    fscanf(in, "%d", &n);

    long a[n+1];
    for(int i=1; i<=n; i++) fscanf(in, "%ld", &a[i]);

    fscanf(in, "%d", &m);
    for(int i=1; i<=m; i++){
        fscanf(in, "%ld %ld", &l, &x);
        if(l==0) fprintf(out, "%d\n", binKer_0(a, x, n));
        if(l==1) fprintf(out, "%d\n", binKer_1(a, x, n));
        if(l==2) fprintf(out, "%d\n", binKer_2(a, x, n));
    }

    return 0;
}