Є масив довжини \(n\).

Вам слід відповісти на наступні \(q\) запити:

• скільки чисел з інтервалу [\(l, r\)] мають значення менше \(x\).

Формат вхідних даних

Перший рядок містить довжину масиву \(n\) (\(1 \le n \le 300000\)).

Наступний рядок містить \(n\) чисел.

У наступному рядку задано кількість \(q\) (\(1 ≤ q ≤ 300000\)) запитів.

Кожен з наступних \(q\) рядків містить один запит: три цілих числа \(l, r\) і \(x\) (\(l ≤ r, 1 ≤ x ≤ 10^9\)).

Формат вихідних даних

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

Приклад вхідних даних

8
1 3 2 4 3 10 5 5
4
1 8 5
1 4 3
5 8 9
2 6 4

Приклад вихідних даних

5
2
3
3