D. Сколько чисел в отрезке

Дан массив из $n$ целых чисел и $q$ запросов вида «сколько элементов массива лежит на отрезке $[l; r]$».

Массив не меняется, поэтому его стоит подготовить один раз, а потом отвечать на каждый запрос быстро.

Первая строка содержит число $n$ ($1 \le n \le 10^5$), вторая — $n$ целых чисел, по модулю не больших $10^9$.

Третья строка содержит число $q$ ($1 \le q \le 10^5$). Следующие $q$ строк содержат по два числа $l$ и $r$ ($l \le r$, по модулю не больше $10^9$).

Для каждого запроса выведите одно число.