printРабочее место участника

printЗадачи

2379. Медианный элемент

Ограничения: время – 500ms/1000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Будем называть `i`-й элемент последовательности `a_1,\ a_2,\ …,\ a_N` медианным, если количество элементов, меньших или равных `a_i` среди элементов `a_1,\ a_2,\ …,\ a_{i-1}`, больше или равно количеству элементов, больших или равных `a_i` среди элементов `a_{i+1},\ a_{i+2},\ …,\ a_N`. В последовательности может быть несколько медианных элементов.
Напишите программу, которая находит минимальный индекс медианного элемента.
Первая строка ввода содержит одно целое число `N` (`1\ ≤\ N\ ≤\ 100000`). Вторая строка ввода содержит `N` целых чисел в диапазоне от 1 до `10^9`, разделенных пробелами – последовательность `a_1,\ a_2,\ …,\ a_N`.
Вывести в первой строке одно целое число — минимальный индекс медианного элемента.

Пример ввода 1

4
1 2 5 10

Пример вывода 1

3

Пример ввода 2

4
10 5 2 1

Пример вывода 2

1
Описание подзадач и системы оценивания
Подзадача 1 (50 баллов)
`1\ ≤\ N\ ≤\ 1000`
В этой подзадаче 5 тестов, каждый тест оценивается в 10 баллов. Баллы за каждый тест начисляются независимо.
Подзадача 2 (50 баллов)
Необходимые подзадачи: 1.
`1000\ <\ N\ ≤\ 100000`
В этой подзадаче 10 тестов, каждый тест оценивается в 5 баллов. Баллы за каждый тест начисляются независимо.
По запросу сообщается результат окончательной проверки на каждом тесте для всех подзадач.
loading