On a secret mission to save the environment, Leslie has infiltrated the corrupt, morally bankrupt Savannah Destruction Agency, which is responsible for approving construction permits in the Serengeti. Her mission is to determine the "influence" of each permit and relay the information to her fellow freedom fighters.

The applications are sitting in a pile in order of submission, and have been marked with their priority level. Due to the competition between developers, each application influences all applications submitted after it that have a lower priority, until it encounters one that doesn't.

To determine the pivotal projects, Leslie wants to know the sum of the priorities of all applications each permit application influences.

Input

The first line contains an integer ~n~ (~1 \leq n \leq 10^6~), the number of permit applications.

The second line contains ~n~ integers ~p_1~, ~p_2~, ~...~, ~p_n~ (~1 \leq p_i \leq 10^9~), where ~p_i~ is the priority of the ~i~-th application.

Output

Output ~n~ space-separated integers, with the ~i~-th integer representing the sum of the priorities of all applications it influences.

Example

Input 1

4
5 1 3 2

Output 1

6 0 2 0

• Permit application with priority of 5 influences all other applications, which have sum 6.
• Permit application with priority of 1 influences no applications, as the next application has a higher priority, which is 3.
• Permit application with priority of 3 influences the application with a priority of 2 only, so the sum is 2.
• Permit application with priority of 2 has no applications after it to influence.

Input 2

6
5 3 4 2 1 5

Output 2

10 0 3 1 0 0

Input 3

10
10 9 8 7 6 5 4 3 2 1

Output 3

45 36 28 21 15 10 6 3 1 0