405111: GYM101798 F World Mug (A)

The 2018 WIFA World Mug is around the corner.

The tournament consists of n teams. In each round of the tournament, each team plays against another team. A team that loses a match exits the tournament, while a team that wins a match progresses to the next round. The tournament finishes when one team wins the final match.

In the first round, team 1 plays against team 2, team 3 plays against team 4, and so on. In the second round, the winner of the first match plays against the winner of the second match, and so on as shown in the picture.

Each team has a certain unique strength s_i. Team i will win a match against team j if its strength s_i is greater than team j's strength s_j. The number of goals scored in that match equals |s_i - s_j|.

Given the tournament format, can you calculate the number of goals scored throughout the tournament?

The first line of input contains one integer n (2 ≤ n ≤ 2¹⁸), the number of teams participating in the tournament. It is guaranteed that the number of teams is a power of two (i.e., 2, 4, 8, 16, ...).

The second line contains n distinct integers, the i^th integer is s_i (1 ≤ s_i ≤ 10⁹), the strength of the i^th team.

On a single line, print the number of goals that will be scored in the tournament.

8
100 200 300 400 800 700 600 500

1200