F. Необычный массив
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Васи есть массив, состоящий из $$$n$$$ чисел $$$a_1, a_2, \ldots, a_n$$$. Для каждой позиции $$$i$$$ и для каждого подотрезка массива $$$[l, r]$$$, который содержит позицию $$$i$$$ (то есть, $$$1 \le l \le i \le r \le n$$$), Вася вычисляет значение $$$c_{i, l, r}$$$ следующим образом. Вася выписывает на листочек числа из массива с позиции $$$l$$$ до позицию $$$r$$$, всего $$$len=r-l+1$$$ чисел (среди которых обязательно есть $$$a_i$$$), и сортирует выписанные числа по возрастанию. После чего Вася находит, на какой позиции $$$j$$$ в полученном отсортированном массиве стоит число $$$a_i$$$. Если таких позиций несколько, то среди них он выбирает ту, которая максимизирует расстояние от середины массива — позиции $$$mid = \lceil (len+1) / 2 \rceil$$$ ($$$len / 2 + 1$$$ в случае четного $$$len$$$ и $$$(len+1)/2$$$ в случае нечетного $$$len$$$). Полученное расстояние $$$|j - mid|$$$ и есть искомая величина $$$c_{i,l,r}$$$.

Например, если у Васи был массив $$$a=\{5,1,3,2,1,7\}$$$, а $$$i=2$$$, $$$l=2$$$, $$$r=5$$$, то Вася выпишет на листочек числа $$$\{1,3,2,1\}$$$, отсортирует их и получит массив $$$\{1,1,2,3\}$$$, длина которого равна 4. Середина этого массива находится на позиции $$$4/2+1=3$$$, а искомое число $$$a_i=1$$$ стоит в этом массиве на позициях 1 и 2. Среди этих двух позиций Вася выбирает ту, которая дальше от середины, то есть, позицию 1. Искомая разность между позициями равна 2, и это и есть значение $$$c_{2,2,5}$$$.

Для каждой позиции $$$i$$$ Вася вычисляет величину $$$b_i$$$, которая равна максимуму среди значений $$$c_{i,l,r}$$$ среди всех подотрезков, содержащих позицию $$$i$$$.

Как вы видите, определение числа $$$b_i$$$ достаточно сложное. Помогите Васе вычислить значения $$$b_i$$$ для всех позиций массива.

Входные данные

В первой строке входных данных находится одно целое число $$$n$$$ ($$$1 \le n \le 200\,000$$$) — размер массива Васи.

Во второй строке находится $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — элементы массива.

Выходные данные

В единственной строке выведите $$$n$$$ чисел, $$$i$$$-е из них должно быть равно $$$b_i$$$.

Система оценки

Тесты к этой задаче состоят из семи групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов необходимых групп.

Дополнительные ограничения
ГруппаБаллы$$$n$$$$$$a_i$$$Необх. группыКомментарий
00–––Тесты из условия.
111$$$n \le 50$$$–0
212$$$n \le 1000$$$–0, 1
323$$$n \le 5000$$$–0, 1, 2
417$$$n \le 50000$$$$$$a_i \le 10$$$0
510$$$n \le 50000$$$––Все $$$a_i$$$ различны
613$$$n \le 50000$$$–0, 1, 2, 3, 4, 5
714––0, 1, 2, 3, 4, 5, 6

Примеры
Входные данные
5
5 4 3 2 1
Выходные данные
2 1 1 2 2
Входные данные
7
3 6 5 6 2 1 3
Выходные данные
2 3 1 3 2 3 1
Примечание

Разберем подробнее первый пример.

  1. Для первой позиции Вася рассмотрит все подотрезки, содержащие эту позицию, в частности, подотрезок $$$[1,5]$$$, где $$$l=1$$$ и $$$r=5$$$. Для вычисления $$$c_{i,l,r}=c_{1,1,5}$$$ Вася выпишет числа $$$\{5, 4, 3, 2, 1\}$$$ и после сортировки получит $$$\{1, 2, 3, 4, 5\}$$$. Середина этого массива находится на позиции 3, а искомое число $$$a_1=5$$$ — на позиции 5. Таким образом, $$$c_{1,1,5}=2$$$. Нетрудно заметить, что это число — максимальное среди всех подотрезков, содержащих позицию 1, а значит, $$$b_1=2$$$.
  2. $$$b_2=c_{2,2,4}$$$.
  3. $$$b_3=c_{3,3,5}$$$.
  4. $$$b_4=c_{4,1,4}$$$. Действительно, если выписать числа на подотрезке $$$[1,4]$$$, то получится массив $$$\{5,4,3,2\}$$$, который после сортировки превратится в $$$\{2,3,4,5\}$$$. Середина этого массива находится на позиции $$$3$$$, а искомый элемент $$$a_4=2$$$ — на позиции 1. Таким образом, $$$c_{4,1,4}=2$$$.
  5. $$$b_5=c_{5,1,5}$$$.