H. Median for Every Prefix!
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a permutation $$$P$$$ of length $$$N$$$.

For each prefix of this permutation, you need to compute its median.

Input

The first line contains one integer $$$N$$$ $$$(1 \le N \le 2 \cdot 10^5)$$$ — the length of the permutation.

The second line contains $$$N$$$ integers $$$P_1, P_2, \ldots, P_N$$$ $$$(1 \le P_i \le N)$$$ separated by spaces — the elements of the permutation.

It is guaranteed that all values $$$P_i$$$ are distinct.

Output

Print $$$N$$$ integers $$$M_1, M_2, \ldots, M_N$$$ separated by spaces, where $$$M_i$$$ is the doubled median of the elements $$$P_1, \ldots, P_i$$$ (that is, the median of the first $$$i$$$ elements of the permutation multiplied by $$$2$$$).

Example
Input
7
5 2 1 4 7 6 3
Output
10 7 4 6 8 9 8
Note

The median of a set of $$$k$$$ numbers sorted in nondecreasing order as $$$a_1 \le a_2 \le \ldots \le a_k$$$ is defined as:

  • if $$$k$$$ is odd — the value $$$a_{(k+1)/2}$$$;
  • if $$$k$$$ is even — the arithmetic mean of the values $$$a_{k/2}$$$ and $$$a_{k/2+1}$$$, that is, $$$\dfrac{a_{k/2} + a_{k/2+1}}{2}$$$.

Since the median for even $$$k$$$ may not be an integer, you should output its doubled value — it is always an integer.

Let us consider the first example step by step. At each step $$$i$$$, we consider the prefix of the first $$$i$$$ elements of the permutation sorted in nondecreasing order, and compute its doubled median $$$M_i$$$:

  • $$$i = 1$$$: sorted prefix — $$$[5]$$$, the median is $$$5$$$, $$$M_1 = 2 \cdot 5 = 10$$$.
  • $$$i = 2$$$: sorted prefix — $$$[2, 5]$$$, the median is $$$(2+5)/2$$$, $$$M_2 = 2 + 5 = 7$$$.
  • $$$i = 3$$$: sorted prefix — $$$[1, 2, 5]$$$, the median is $$$2$$$, $$$M_3 = 2 \cdot 2 = 4$$$.
  • $$$i = 4$$$: sorted prefix — $$$[1, 2, 4, 5]$$$, the median is $$$(2+4)/2$$$, $$$M_4 = 2 + 4 = 6$$$.
  • $$$i = 5$$$: sorted prefix — $$$[1, 2, 4, 5, 7]$$$, the median is $$$4$$$, $$$M_5 = 2 \cdot 4 = 8$$$.
  • $$$i = 6$$$: sorted prefix — $$$[1, 2, 4, 5, 6, 7]$$$, the median is $$$(4+5)/2$$$, $$$M_6 = 4 + 5 = 9$$$.
  • $$$i = 7$$$: sorted prefix — $$$[1, 2, 3, 4, 5, 6, 7]$$$, the median is $$$4$$$, $$$M_7 = 2 \cdot 4 = 8$$$.