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

У Васи есть массив, состоящий из $$$n$$$ чисел $$$a_1, a_2, \ldots, a_n$$$. Каждое число в этом массиве Вася считает по-своему необычным. Чтобы вычислить необычность числа на позиции $$$i$$$, Вася делает следующее:

Он выбирает подотрезок $$$a_l, a_{l+1}, \ldots, a_r$$$ такой, что $$$1 \le l \le i \le r \le n$$$ и мысленно сортирует его по возрастанию (равные элементы он может переставлять так, как ему хочется). Далее на этом подотрезке он находит центр. Центром подотрезка называется элемент на позиции $$$(l + r) / 2$$$, если длина отрезка нечётна, или элемент на позиции $$$(l + r + 1) / 2$$$, если длина отрезка чётна. Теперь Вася находит на этом подотрезеке элемент, который до сортировки стоял на позиции $$$i$$$, и смотрит на расстояние от этого элемента до центра подотрезка (расстояние между элементами с индексами $$$j$$$ и $$$k$$$ равняется $$$|j - k|$$$).

Необычностью числа на позиции $$$i$$$ называется максимальное такое расстояние среди всех подходящих выборов $$$l$$$ и $$$r$$$.

Вася хочет посчитать необычность каждого числа в своём массиве. Помогите ему это сделать.

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

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

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

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

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

Примеры
Входные данные
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$$$. Если его отсортировать, то числа упорядочатся по значению как $$$[1, 2, 3, 4, 5]$$$, центр будет равен $$$3$$$, таким образом расстояние от центра до числа $$$5$$$ равно $$$2$$$.
  2. Для второй позиции подойдёт отрезок от позиции $$$2$$$ до позиции $$$4$$$.
  3. Для третей позиции подойдёт отрезок от позиции $$$3$$$ до позиции $$$5$$$.
  4. Для четвёртой позиции подойдёт отрезок от позиции $$$1$$$ до позиции $$$4$$$. Если его отсортировать, то числа упорядочатся по значению как $$$[2, 3, 4, 5]$$$, центр будет равен $$$4$$$, таким образом расстояние от центра до числа $$$2$$$ равно $$$2$$$.
  5. Для пятой позиции подойдёт отрезок от позиции $$$1$$$ до позиции $$$5$$$.