bound.cpp

#include <stdio.h>

int n, arr[1000000], k, str[100000][20], il, iu;

void lower_bound(int left, int right, int number)
{
	int mid = (left + right) / 2;
	if (left >= right) {
		il = left;
		return;
	}
	if (arr[mid] < number) {
		lower_bound(mid + 1, right, number);
	}
	else
		lower_bound(left, mid, number);
}

void upper_bound(int left, int right, int number)
{
	int mid = (left + right) / 2;
	if (left >= right) {
		iu = left;
		return;
	}
	if (arr[mid] <= number) {
		upper_bound(mid + 1, right, number);
	}
	else
		upper_bound(left, mid, number);
}

int main()
{
	scanf("%d", &n);
	for (int i = 0; i<n; i++) {
		scanf("%d", arr + i);
	}
	scanf("%d", &k);
	for (int i = 0; i<k; i++) {
		for (int j = 0; j<2; j++) {
			scanf("%d", &str[i][j]);
		}
	}
	for (int i = 0; i<k; i++) {
		lower_bound(0, n, str[i][0]);
		upper_bound(0, n, str[i][1]);
		printf("%d\n", iu - il);
	}
}