Fişierul intrare/ieşire:competition.in, competition.outSursăTuymaada 2019
AutorAlexandru PetrescuAdăugată dealexpetrescuAlexandru Petrescu alexpetrescu
Timp execuţie pe test1.375 secLimită de memorie262144 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Competition

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.

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 22 + 32 + 22 = 4 + 9 + 4 = 17. The outcome of the competition is the sum of happiness for all participants.

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.

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).

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 42 = 16. Participant number 1 receives a coin on day 4. His happiness is 12 = 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.

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.

Output

Output file competition.out contains N + 1 lines. Line i contains number f(i - 1).

Constraints

  • 1 ≤ N ≤ 106
  • 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

Exemplu

competition.incompetition.out
4
0 4 4 4
20
20
21
21
20
4
1 0 1 1
21
17
17
27
26
4
2 1 1 0
23
23
27
21
21

Tutorial

You can see a solution description in problem's editorial

Request

Contacteaza-l pe autor daca te oferi sa traduci enuntul in limba romana.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?