34789번 - $K^{\text{th}}$ King 다국어

문제

Samuel recently became the 1ドル^{\text{st}}$ king in the distant country of Reyjrland (pronounced "Ragerland"). He must make sure that the cities represent his likeness as part of the "Inaugural Collection of Preparatory Chores" needed to be done by the king.

Reyjrland can be represented as an array of integers of length $n,ドル corresponding to the values of the $n$ cities in the country. If we define $f(b, k)$ to be the $k^\text{th}$ largest value in an array $b$ of length at least $k,ドル then the cities are said to represent the $k^{\text{th}}$ king's likeness if $f(b, k)$ is the same for all subarrays$^{\dagger}$ $b$ of $a$ which are of length at least $k$.

The current values of the cities, $a$ may not yet represent the king's likeness. To fix this, each day, the king may choose a city and increment or decrement the city's values by 1.

After working for many days inefficiently randomly modifying the values on cities until the array represented his likeness, Samuel swore he would never let future kings go through the same thing. He tasks you to find the minimum number of days to transform the current city values into an array that represents the $k^{\text{th}}$ king, for all $k$ from 1ドル$ through $n$. Modifications from making the array represent the likeness of the $k^{\text{th}}$ king do not carry over to any other king. That is, after each king's reign, the city values are reset to the values in the original array $a$.

$^\dagger$: An array $b$ is a subarray of an array $a$ if $b$ can be obtained from $a$ by deleting several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end. In particular, an array is a subarray of itself.

입력

The first line of input contains one integer $n$ (1ドル \le n \le 2\cdot 10^5$), the number of cities which is also the length of the array of values.

The next $n$ lines contain one integer each. The $i^{\text{th}}$ line contains $a_i$ (0ドル \le a_i \le 10^9$), the value of the $i^{\text{th}}$ city.

출력

Output $n$ lines containing one integer each. The $k^{\text{th}}$ line should contain the minimum number of days for the $k^{\text{th}}$ king to make the array represent his likeness.

제한

노트