Інтервальний запит менше

Маємо масив цілих чисел довжини $n$. Вам потрібно відповісти на $q$ запитів: скільки чисел в інтервалі $[l,r]$ мають значення менше $x$.

Вхідні дані

Перший рядок містить довжину масиву $n(1\le n\le 2\cdot 10^5)$. Другий рядок містить $n$ чисел. У третьому рядку вказано кількість запитів $q(1\le q\le 10^5)$. Кожен з наступних $q$ рядків містить один запит у вигляді трьох цілих чисел $l,r$ і $x(l\le r,1\le x\le 10^9)$.

Вихідні дані

Для кожного запиту виведіть в окремому рядку кількість чисел в інтервалі $[l,r]$, які менші за $x$.

Приклади