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 Ai, 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 Si, Ei, Ki, (1 ≤ Si ≤ Ei ≤ N), pooddzielanych pojedynczymi odstępami i określających zapytanie o K-tą statystykę pozycyjną w spójnym podciągu od Si-tego do Ei-tego elementu ciągu.
Dane są dobrane w taki sposób, aby każda statystyka pozycyjna istniała: 1 ≤ Ki ≤ Ei − Si + 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ść Ki-tej statystyki pozycyjnej spójnego podciągu od Si-tego do Ei-tego elementu ciągu.
Ograniczenia
1 ≤ N ≤ 250 000, 1 ≤ Q ≤ 15 000, 1 ≤ Ai ≤ 109.
W testach wartych łącznie 25% maksymalnej punktacji zachodzi dodatkowy warunek: N ≤ 2 000.\ W testach wartych łącznie 40% maksymalnej punktacji zachodzi dodatkowy warunek: Ai ≤ 106.\ 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
| Input | Output | |
|
|