A running club is recruiting members and growing rapidly, with exactly one new member joining each day. Every member comes with a specific initial skill level, and they are assigned a unique ID based on the order of their arrival.

At the end of every day, the Coach likes to calculate a metric he calls the "total potential" of the club. This value is simply the sum of the individual potentials of all current members. To keep the members motivated, the potential of a member is calculated through a hypothetical "what-if" scenario involving a single, intense workout.

In this imaginary workout, a member can choose to put in a certain amount of effort to temporarily boost their skill level. For every $1$ unit of effort they expend, their skill level increases by exactly $1$ unit. In return, they gain $1$ unit of "happiness" for every other member currently in the club who:

• joined the club strictly after they did; and
• was originally strictly more skilled than they were, but has now been caught or surpassed thanks to the workout.

Note that during this calculation, only that member's skill level is increased, while the skill levels of all other members remain fixed at their original values.

The potential of a single member is defined as the maximum possible value of their net gain (happiness minus effort) they could achieve by choosing their effort level optimally. These workouts are entirely theoretical; they are used only for the Coach's daily report, and the members' actual skill levels remain unchanged from day to day.

Your task is to help the Coach calculate the total potential of the club at the end of each day of the recruiting period.

Input

The first line of input contains an integer $n$ ($1 \le n \le 10^5$), representing the number of days the club is recruiting members.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$), where $a_i$ is the initial skill level of the member who joins on day $i$.

Output

Output $n$ integers in a single line. The $k$-th integer should be the total potential of the club at the end of day $k$.

Examples

Input 1

8
1 2 3 1 2 3 2 3

Output 1

0 0 0 0 1 3 5 9

Input 2

1
1

Output 2

0

Notes

Explanation of Sample 1: On day $5$, there are $5$ members with skill levels $[1, 2, 3, 1, 2]$. For member $1$: There are $3$ members joining later with strictly higher skills: member $2$, member $3$, and member $5$. The maximum potential for member $1$ is $1$, achieved by either of the following strategies:

• If member $1$ pays $1$ unit of effort, their skill becomes $2$. They will catch or surpass member $2$ and member $5$. The happiness is $2$ units, and the gain is $2 - 1 = 1$ unit.
• If member $1$ pays $2$ units of effort, their skill becomes $3$. They will catch or surpass members $2$, $3$, and $5$. The happiness is $3$ units, and the gain is $3 - 2 = 1$ unit.

The other members have maximum potential $0$. Hence, the total potential for day $5$ is $1$.

On day $8$, there are $8$ members with skill levels $[1, 2, 3, 1, 2, 3, 2, 3]$. The optimal efforts are $[2, 1, 0, 2, 1, 0, 1, 0]$ and the corresponding maximum potentials are $[4, 2, 0, 2, 1, 0, 0, 0]$.