H. Каждому префиксу по медиане!
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дана перестановка $$$P$$$ длины $$$N$$$.

Для каждого префикса этой перестановки требуется вычислить его медиану.

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

В первой строке задано одно целое число $$$N$$$ $$$(1 \le N \le 2 \cdot 10^5)$$$ — длина перестановки.

Во второй строке через пробел задано $$$N$$$ целых чисел $$$P_1, P_2, \ldots, P_N$$$ $$$(1 \le P_i \le N)$$$ — элементы перестановки.

Гарантируется, что все значения $$$P_i$$$ различны.

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

Выведите через пробел $$$N$$$ целых чисел $$$M_1, M_2, \ldots, M_N$$$, где $$$M_i$$$ — удвоенная медиана элементов $$$P_1, \ldots, P_i$$$ (то есть медиана первых $$$i$$$ элементов перестановки, умноженная на $$$2$$$).

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

Медианой набора из $$$k$$$ чисел, упорядоченных по неубыванию как $$$a_1 \le a_2 \le \ldots \le a_k$$$, называется:

  • если $$$k$$$ нечётно — значение $$$a_{(k+1)/2}$$$;
  • если $$$k$$$ чётно — среднее арифметическое значений $$$a_{k/2}$$$ и $$$a_{k/2+1}$$$, то есть $$$\dfrac{a_{k/2} + a_{k/2+1}}{2}$$$.

Поскольку медиана при чётном $$$k$$$ может быть нецелой, в качестве ответа нужно вывести её удвоенное значение — оно всегда является целым числом.

Рассмотрим первый пример по шагам. На каждом шаге $$$i$$$ рассматривается отсортированный по неубыванию набор первых $$$i$$$ элементов перестановки, и вычисляется его удвоенная медиана $$$M_i$$$:

  • $$$i = 1$$$: отсортированный префикс — $$$[5]$$$, медиана равна $$$5$$$, $$$M_1 = 2 \cdot 5 = 10$$$.
  • $$$i = 2$$$: отсортированный префикс — $$$[2, 5]$$$, медиана равна $$$(2+5)/2$$$, $$$M_2 = 2 + 5 = 7$$$.
  • $$$i = 3$$$: отсортированный префикс — $$$[1, 2, 5]$$$, медиана равна $$$2$$$, $$$M_3 = 2 \cdot 2 = 4$$$.
  • $$$i = 4$$$: отсортированный префикс — $$$[1, 2, 4, 5]$$$, медиана равна $$$(2+4)/2$$$, $$$M_4 = 2 + 4 = 6$$$.
  • $$$i = 5$$$: отсортированный префикс — $$$[1, 2, 4, 5, 7]$$$, медиана равна $$$4$$$, $$$M_5 = 2 \cdot 4 = 8$$$.
  • $$$i = 6$$$: отсортированный префикс — $$$[1, 2, 4, 5, 6, 7]$$$, медиана равна $$$(4+5)/2$$$, $$$M_6 = 4 + 5 = 9$$$.
  • $$$i = 7$$$: отсортированный префикс — $$$[1, 2, 3, 4, 5, 6, 7]$$$, медиана равна $$$4$$$, $$$M_7 = 2 \cdot 4 = 8$$$.