|
Супермедиана
(Время: 3 сек. Память: 128 Мб Сложность: 66%)
Медианой набора чисел размера K является число, которое будет стоять на позиции ⌊(K + 1)/2⌋, если числа упорядочить по неубыванию (позиции нумеруются с 1). Например, медианой {1, 5, 2} будет 2, медианой {4, 2, 8, 6} будет 4, а медианой {1, 3, 1, 3, 3} будет 3.
Дан массив различных чисел A размера N. Рассмотрим каждый отрезок [L, R] (1 ⩽ L ⩽ R ⩽ N) и выпишем медиану чисел с этого отрезка, то есть медиану {AL, AL+1, ..., AR}. Ваша задача — вычислить медиану выписанных чисел.
Входные данные
Первая строка входного файла INPUT.TXT содержит целое число T — количество наборов входных данных (1 ⩽ T ⩽ 50 000).
Каждый набор состоит из двух строк: в первой содержится целое число N (1 ⩽ N ⩽ 100 000), а во второй N целых различных чисел Ai (1 ⩽ Ai ⩽ N).
Гарантируется, что сумма N в одном тесте не превосходит 500 000.
Выходные данные
На каждый набор входных данных выведите в выходной файл OUTPUT.TXT ответ в отдельной строке.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 3
3
1 2 3
6
2 5 1 4 6 3
6
3 5 6 4 1 2 | 2
3
4 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
