Problem Description

Reyjrland is represented by an integer array $a$ of length $n$, where each element is the value of one city. For any array $b$ of length at least $k$, let $f(b,k)$ be its $k$th-largest value.

The cities represent the likeness of the $k$th king if $f(b,k)$ is the same for every contiguous subarray $b$ of $a$ whose length is at least $k$. A subarray is obtained by deleting zero or more elements from the beginning and zero or more elements from the end; an array is a subarray of itself.

Each day, the king may increase or decrease one city value by $1$. For every $k$ from $1$ through $n$, find the minimum number of days needed to modify the original array so that it represents the likeness of the $k$th king. Modifications for one value of $k$ do not carry over to another: the array is reset to its original values each time.

Input Format

The first line contains an integer $n$ ($1\le n\le2\cdot10^5$).

Each of the next $n$ lines contains one integer $a_i$ ($0\le a_i\le10^9$).

Output Format

Output $n$ lines. Line $k$ contains the minimum number of days needed for the $k$th king.

3
2
3
1

2
1
0

4
1000000000
1
1000000000
1

1999999998
999999999
0
0