B. Сколько раз встречается максимум

Для каждого запроса нужно сказать, сколько элементов отрезка равны его максимуму.

В первой строке - число $N$ ($1 \le N \le 10^5$).

Во второй - $N$ чисел от 1 до $10^5$.

В третьей - число запросов $K$ ($1 \le K \le 30\,000$), далее $K$ строк с парами $l$ и $r$.

Для каждого запроса выведите количество элементов, равных максимуму на отрезке. Числа выводите в одну строку через пробел.