H. Статистика: сколько раз

1000 мс · 256 МБ · всё или ничего

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

На каждый запрос $(l, r, x)$ ответьте, сколько городов с номерами от $l$ до $r$ перевезли ровно $x$ человек.

Формат ввода

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

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

Формат вывода

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

Примеры

ввод

5
123 666 314 666 434
5
1 5 314
1 5 578
2 4 666
4 4 713
1 5 666

вывод

Войдите, чтобы отправлять решения.