== include(page="template/taskheader" task_id="competition") ==

Poveste şi cerinţă...

There are $N+1$ people competing in some event for $N$ days. Each day, exactly one of them is declared the winner of the day. The score of some participant is equal to the number of days he was winner. After each day, the participants with the highest score receive a coin. After the competition is over, each participant has some happiness value, calculated the following way: for every discretely continuous maximal interval when he receives coin, add to his happiness the square of the length of the interval.

h2. Date de intrare

For example, if some contestant won coins on days $3, 4, 10, 11, 12, 18$ and $19$, the intervals are $[3-4]$, $[10-12]$ and $[18-19]$, while his happiness is equal to $2^2^ + 3^2^ + 2^2^ = 4 + 9 + 4 = 17$. The outcome of the competition is the sum of happiness for all participants.

Fişierul de intrare $competition.in$ ...

Now Marcel comes in, and he is able to insert, somewhere in the array of days, one day that will surely be won by participant number $0$.

h2. Date de ieşire

You are given an array of $N$ integers between $0$ and $N$, representing the winner of each day. Let $f(p)$ = the outcome of the competition if we would insert number $0$ in this array after the $p$'th element in the array. You need to print numbers $f(0), f(1), ..., f(N)$.

În fişierul de ieşire $competition.out$ ...

For example, if the array of $3$ elements is $0$ $1$ $1$, $f(0)$ = the outcome of the competition $*0* 0 1 1$. Participant number $0$ receives coins in the days $1$, $2$, $3$ and $4$. So his happiness is $4^2^ = 16$. Participant number $1$ receives a coin on day $4$. His happiness is $1^2^ = 1$. Participants $2$ and $3$ receive no coins. So $f(0) = 17$. $f(N = 3)$ = the outcome of the competition $0 1 1 *0*$. Participant number $0$ receives coins in the days $1, 2, 4$ so his happiness is $4 + 1 = 5$. Participant number $1$ receives coins in the days $2, 3, 4$ so his happiness is $9$. So $f(3) = 14$.

h2. Restricţii

h2. Input

* $... ≤ ... ≤ ...$

The first line of input file $competition.in$ contains a number $N$, and on the following line there are $N$ numbers with values between $0$ and $N$, representing the winners of the competition on each day.
 
h2. Output
 
Output file $competition.out$ contains $N + 1$ lines. Line $i$ contains number $f(i - 1)$.
 
h2. Constraints
 
* $1 ≤ N ≤ 10^6^$
* For $8$ points, $N ≤ 10$
* For $20$ points, $N ≤ 100$
* For $40$ points, $N ≤ 1.000$
* For $68$ points, $N ≤ 100.000$
* Note that the scoring is not the same as the one in the official onsite contest

h2. Exemplu
table(example). |_. competition.in |_. competition.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 4
0 4 4 4
| 0

|

| 4
1 0 1 1
| 0
|
| 4
2 1 1 0
| 0
|

h3. Explicaţie