시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 512 MB 3 1 1 33.333%

문제

The teams in your local rugby league aren’t particularly good, but they make up for it in enthusiasm. We are going to organise a single-elimination knockout tournament between them, where the 2n teams play n rounds. In each round, the 2i + 1th remaining team pairs up with the 2i + 2th team and one or the other team is eliminated.

Each team has a scalar skill level. In the normal course of things, a team with higher skill level will always beat a team with lower skill level. However, training plays a part too: if one team studies another, learns its techniques, and trains against them, it can win.

The number of hours a team with skill a must train to beat a team with skill b (where a ≤ b) is |b − a|2. This training only affects that one game (it does not transfer to other teams).

You would quite like your favourite team to win the tournament. If you take complete control over how every team trains, you can always make this happen. What is the minimum number of hours needed, in total across all teams, in order for your team (team 1) to win?

입력

The input consists of:

  • one line containing the integer r (1 ≤ r ≤ 14), the number of rounds in the tournament.
  • one line with 2r integers s1 . . . s2s (0 ≤ si ≤ 106 for each i), where si is the skill level of the ith team.

출력

Output the smallest number of hours needed for team 1 to win the tournament.

예제 입력 1

1
50 40

예제 출력 1

0

예제 입력 2

3
1 2 3 4 8 7 6 5

예제 출력 2

28