As the new school year begins, the school is hosting a grand "Rock, Paper, Scissors" tournament to welcome everyone back. ~N~ students will participate in the tournament, where ~N~ is a power of ~2~. Each student has a unique skill level from ~1~ to ~N~, and when two students are matched against each other, the student with the higher skill level always wins. The students have been put into a specific order that was previously chosen by the organizers. The computer managing the tournament stores the details of the students in an array ~A_1~, ~A_2~, ~A_3~, ..., ~A_N~, where ~A_i~ is the skill of the ~i~-th student. The computer will match the students as follows:

• The 1st student is matched against the 2nd student, the 3rd student is matched against the 4th student, the 5th student is matched against the 6th student, the 7th student is matched against the 8th student, and so on. The loser of each of the matches are then eliminated, whereas the winners progress to the next round.
• The winner of the match between the 1st and 2nd student is matched against the winner of the match between the 3rd and 4th student, the winner of the match between the 5th and 6th student is matched against the winner of the match between the 7th and 8th student, and so on. Again, the losers are eliminated, and the winners progress to the next round.
• This continues until there is one student remaining: the winner of the tournament.

In other words, the tournament is held in a single-elimination format.

Let the underwhelmingness of a match be defined as the square of the difference between the skills of the students in a match. Let inserting an element ~x~ in an array ~B~ at a index ~i~ mean placing ~x~ at the ~i~-th position in ~B~, and shifting all subsequent elements one position to the right.

After a brief power outage, the memory of the computer has become corrupted, and a random student has been deleted from ~A~! To recover the original array ~A~, the missing student must be reinserted into the array. For every ~i~ between ~1~ and ~N~, determine the sum of the underwhelmingness of all matches played if the missing student was inserted at position ~i~.

Constraints

~4 \leq N \leq 2^{18}~

~1 \leq A_i \leq N~

~N~ is a power of ~2~.

No two elements in ~A~ are equal.

Input Specification

The first line of input contains one integer ~N~, the number of students participating in the tournament.

The second line of input contains ~N - 1~ integers, the array ~A~ after a random student has been removed.

Output Specification

On one line, for every ~i~ between ~1~ and ~N~, print the sum of the underwhelmingness of all matches played if the missing student was inserted at position ~i~.

Sample Input

4
2 4 3

Sample Output

6 6 9 9

Explanation for Sample

The student that has been deleted has skill level ~1~.

If the missing student was inserted at index ~1~, the array ~A~ would be ~[1, 2, 4, 3]~. The ~1~st student would be matched against the ~2~nd student, and the ~3~rd student would be matched against the ~4~th student. The ~2~nd and ~3~rd students progress to the next round, where they would be matched against each other. The ~3~rd student has a higher skill level than the ~2~st student, and is the overall winner of the tournament. The sum of the underwhelmingness of all matches would be ~(1 - 2)^2 + (4 - 3)^2 + (2 - 4)^2 = 6~.

If the missing student was inserted at index ~2~, the array ~A~ would be ~[2, 1, 4, 3]~, and the sum of the underwhelmingness of all matches is ~(2 - 1)^2 + (4 - 3)^2 + (2 - 4)^2 = 6~.

If the missing student was inserted at index ~3~, the array ~A~ would be ~[2, 4, 1, 3]~, and the sum of the underwhelmingness of all matches is ~(2 - 4)^2 + (1 - 3)^2 + (4 - 3)^2 = 9~.

If the missing student was inserted at index ~4~, the array ~A~ would be ~[2, 4, 3, 1]~, and the sum of the underwhelmingness of all matches is ~(2 - 4)^2 + (3 - 1)^2 + (4 - 3)^2 = 9~.