Реалізуйте запити K-те число на відрізку.

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

В першому рядку ціле число \(N\), кількість елементів масиву (\(1 \le N \le 10^5\)).
В другому рядку елементи масиву. (\(1 \le Ai \le 10^5\))
В третьому рядку вводиться число \(Q\) - кількість запитів (\(1 \le Q \le 10^5\))
В кожному з наступних \(Q\) рядків міститься по три цілих числа \(L,R,K\) - номера лівого і правого елементів відрізка масиву , на якому треба знайти K-й за величиною елемент.

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

Для кожного запиту виведіть відповідь в окремому рядку.

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

7
1 5 2 6 3 7 4
3
2 5 3
4 4 1
1 7 3

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

5
6
3