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

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

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

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

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

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

Кожен з наступних \(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