Сколько меньших на отрезке

Дан массив, который не меняется. Для каждого запроса $(l, r, x)$ выведите, сколько элементов на отрезке $[l, r]$ строго меньше $x$. Все запросы известны заранее.

Ещё один офлайн-приём: отсортировать всё по значению.

В первой строке $n$ ($1 \le n \le 10^5$). Во второй — $n$ чисел $a_i$ ($|a_i| \le 10^9$). В третьей — $m$ ($1 \le m \le 10^5$). Далее $m$ строк по три числа $l$, $r$, $x$ ($1 \le l \le r \le n$, $|x| \le 10^9$).

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