#include <iostream>
//#include <fstream>
#include <cstdio>

FILE* in;
FILE* out;

using namespace std;

long 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, k;
    while(bal<jobb){
        k=(bal+jobb)/2;
        if(a[k]<=x) bal=k+1;
        else jobb=k;
    }
    k=(bal+jobb)/2;
    if(a[k]>x) k--;
    return k;
}

int binKer_2(long a[], long x, int n)
{
    int bal=1, jobb=n, k;
    while(bal<jobb){
        k=(bal+jobb)/2;
        if(a[k]<x) bal=k+1;
        else jobb=k;
    }
    k=(bal+jobb)/2;
    if(a[k]<x) k++;
    return k;
}


int main()
{
    in=fopen("cautbin.in", "r");
    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, "%d", &a[i]);
    fscanf(in, "%d", &m);
    for(int i=1; i<=m; i++){
        //in>>l; in>>x;
        fscanf(in, "%d %d", &l, &x);
        if(l==0) fprintf(out, "%d \n", binKer_0(a,x,n)); //out<<binKer_0(a, x, n)<<endl;
        if(l==1) fprintf(out, "%d \n", binKer_1(a,x,n)); //out<<binKer_1(a, x, n)<<endl;
        if(l==2) fprintf(out, "%d \n", binKer_2(a,x,n)); //out<<binKer_2(a, x, n)<<endl;
    }
    return 0;
}