#include <fstream>
#include <iostream>
#include <cstdio>
using namespace std;
int n,a[100001], m;



inline int BS2(int x)
{
    int lo, hi, mid, last = 0;
 
    for (lo = 1, hi = n; lo <= hi; )
    {
        mid = lo + (hi-lo) / 2;
        if (a[mid] <= x) last = mid, lo = mid+1;
        else hi = mid-1;
    }
    return last;
}
 
inline int BS3(int x)
{
    int lo, hi, mid, last = n+1;
 
    for (lo = 1, hi = n; lo <= hi; )
    {
        mid = lo + (hi-lo) / 2;
        if (x <= a[mid]) last = mid, hi = mid-1;
        else lo = mid+1;
    }
    return last;
}


inline int BS1(int x)
{
    int lo, hi, mid;
 
    for (lo = 1, hi = n; lo <= hi; )
    {
        mid = lo + (hi-lo) / 2;
        if (x < a[mid]) hi = mid-1;
        else if (a[mid] < x) lo = mid+1;
        else return mid;
    }
    return -1;
}


inline int f0(int x){
	int st=1,dr=n,rez = -1;
	while(st<=dr){
		int m = st+(dr-st)/2;
//		cout<<m<<" ";
		if( a[m] == x)
			 rez = m;
		if(a[m]<x)
				 st = m+1;
		else
			dr= m-1;
	}
	return rez;
}
inline int f1(int x){
	int st=1,dr=n,rez;
	while(st<=dr){
		int m = st+(dr-st)/2;
		if(a[m]<=x)
			rez = m, st= m+1;
		else
			dr = m-1;
	}
	return rez;
}
inline int f2(int x){
	int st=1,dr=n, rez;
	while(st<=dr){
		int m =st+(dr-st)/2;
		if(a[m]>=x)
			rez = m , dr = m-1;
		else
			st = m+1;

	}
	return rez;
}
int main2(){
 int i, t, x;
     
	ifstream fin("cautbin.in");
	ofstream fout("cautbin.out");
	
    fin >> n;
    for (i = 1; i <= n; ++i)
        fin >> a[i];
         
    fin >> m;
    for (; m; --m)
    {
        fin >> t >> x;
        if (!t)
            fout << BS1(x) << endl;
        else if (t == 1)
            fout << BS2(x) << endl;
        else
            fout << BS3(x) << endl;
    }
	return 0;
}

int main()
{
    int i, t, x;
     
    FILE *f = fopen("cautbin.in", "r");
	FILE *out = fopen("cautbin.out", "w");
	
    
 
    fscanf(f, "%d", &n);   
    for (i = 1; i <= n; ++i)
        fscanf(f, "%d", &a[i]);
         
    fscanf(f, "%d", &m);
    for (; m; --m)
    {
        fscanf(f, "%d %d", &t, &x);
        if (!t)
            fprintf(out, "%d\n", BS1(x));
        else if (t == 1)
            fprintf(out, "%d\n", BS2(x));
        else
            fprintf(out, "%d\n", BS3(x));
    }
	return 0;
}