Problem description

Dany jest ciąg liczb całkowitych oraz dużo zapytań o statystyki pozycyjne pewnego spójnego podciągu zadanego ciągu liczb.

K-tą statystyką pozycyjną ciągu nazywamy K-ty najmniejszy jego element (K-ty element w posortowanym ciągu). Na przykład 2-gą statystykę pozycyjną ciągu (1,5,3,9,10), jest 3.

Napisz program, który: wczyta ciąg liczb oraz zapytania, dla każdego zapytania wyznaczy odpowiednią statystykę pozycyjną i wypisze wyniki na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba naturalna N, określająca liczbę elementów ciągu. W drugim wierszu wejścia znajduje się ciąg N nieujemnych liczb całkowitych A_i, pooddzielanych pojedynczymi odstępami.

W trzecim wierszu wejścia znajduje się jedna liczba naturalna Q, określająca liczbę zapytań. W kolejnych Q wierszach znajduje się opis kolejnych zapytań. Opis każdego zapytania składa się z trzech liczb naturalnych S_i, E_i, K_i, (1 ≤ S_i ≤ E_i ≤ N), pooddzielanych pojedynczymi odstępami i określających zapytanie o K-tą statystykę pozycyjną w spójnym podciągu od S_i-tego do E_i-tego elementu ciągu.

Dane są dobrane w taki sposób, aby każda statystyka pozycyjna istniała: 1 ≤ K_i ≤ E_i − S_i + 1.

Wyjście

Twój program powinien wypisać na wyjście dokładnie Q wierszy. W i-tym wierszu powinna się znaleźć odpowiedź dla i-tego zapytania. Odpowiedź dla i-tego zapytania to jedna liczba naturalna – wartość K_i-tej statystyki pozycyjnej spójnego podciągu od S_i-tego do E_i-tego elementu ciągu.

Ograniczenia

1 ≤ N ≤ 250 000, 1 ≤ Q ≤ 15 000, 1 ≤ A_i ≤ 10⁹.

W testach wartych łącznie 25% maksymalnej punktacji zachodzi dodatkowy warunek: N ≤ 2 000.\ W testach wartych łącznie 40% maksymalnej punktacji zachodzi dodatkowy warunek: A_i ≤ 10⁶.\ W testach wartych łącznie 50% maksymalnej punktacji zachodzi dodatkowy warunek: N ≤ 50 000.\ W testach wartych łącznie 65% maksymalnej punktacji zachodzi dodatkowy warunek: Q ≤ 2 000.

Przykład

5
3 1 10 3 5
3
1 3 2
1 4 3
3 5 2

3
3
5