Problem description
Na taśmie o wymiarach N × 1 pól znajdują się liczby naturalne, po jednej liczbie na jednym polu taśmy.
Twoim zadaniem jest (efektywnie) obsłużyć wiele zapytań o różne spójne fragmenty tej taśmy. W każdym zapytaniu rozpatrywany jest fragment od Si-tego do Ei-tego pola taśmy włącznie. Pytanie dotyczy tego jaka jest mediana zbioru {T[Si], T[Si+1], …, T[Ei]}. Zwróć uwagę na pogrubione słowo zbioru: powtórzone elementy na taśmie występują w zbiorze jedynie jeden raz.
Dla przypomnienia: mediana zbioru M-elementowego to średnia arytmetyczna co najwyżej dwóch środkowych elementów zbioru po jego posortowaniu: jeżeli elementy zbioru to X[1] < X[2] < … < X[M] to mediana wynosi $\frac{X[\lfloor (M+1)/2 \rfloor] + X[\lceil (M+1)/2 \rceil]}{2}$.
Napisz program, który: wczyta liczby zapisane na taśmie oraz zapytania, dla każdego zapytania ustali medianę odpowiedniego podzbioru liczb z taśmy i wypisze wyniki na standardowe wyjście.
Wejście
W pierwszym wierszu wejścia znajduje się jedna liczba naturalna N, określająca długość taśmy. W drugim wierszu wejścia znajduje się ciąg N liczb naturalnych T[i], pooddzielanych pojedynczymi odstępami. Są to liczby zapisane na taśmie. 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ń, po jednym w wierszu.
Opis każdego zapytania składa się z dwóch liczb naturalnych Si oraz Ei oddzielonych pojedynczym odstępem. Jest to zapytanie o medianę zbioru {T[Si], T[Si+1], …, T[Ei]}.
Wyjście
Twój program powinien wypisać na wyjście dokładnie Q wierszy. W i-tym wierszu wyjścia powinna się znaleźć odpowiedź dla i-tego zapytania: liczba rzeczywista, wypisana z dokładnością do jednego miejsca po kropce dziesiętnej, reprezentująca medianę podzbioru z danego zapytania.
Ograniczenia
1 ≤ N ≤ 200 000, 1 ≤ Q ≤ 200 000, 1 ≤ T[i] ≤ 109, 1 ≤ Si ≤ Ei ≤ N.
Częściowa punktacja
W pewnym podzbiorze testów wartych łącznie 50% maksymalnej punktacji zachodzi dodatkowy warunek: wszystkie liczby na taśmie są parami różne.
Przykład
| Wejście | Wyjście | |
|
|