Given the values at the leaf nodes of a complete binary tree. The total number of nodes in the binary tree, is also given. Sum of the values at both the children of a node is equal to the value of the node itself. You can add any value or subtract any value from a node. Print the minimum change(difference made) in the sum of values of all the nodes in the tree, such that all the leaf nodes have the same value.

Note: If a value transfers from one node to another, then that is not a change, but if an extra is needed to be added or subtracted to the entire total value of the nodes, then that is a change.

Input Description:

Input will contain an integer N, the number of nodes in the tree on a newline, followed by N space separated integers representing the values at the leaf nodes of the tree.

Output Description:

Print the required value on a newline.

Constraints:

1<=N<=20000
1<=Value at each node in the leaves<=1000

Example 1:
Input:

1

50
Output:

0

Explanation: Since there is only one node, it is a leaf node itself and no change needs to be made.

Example 2:
Input:

3

200 800
Output:

0

Explanation: There are two leaf nodes, and they can be made to 500 500, since no change in the total was made so difference made is 0.

Example 3:
Input:

30

29 33 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
Output:

6

Output: A total change of 6 needs to be changed to the entire value of the nodes, to get the leaf nodes equal.

见题面

见题面