You are given an array of n integers. Your task is to calculate the value of the array using the divide and conquer method.

For a segment [left, right]:

• If the segment contains only one element, its value is equal to that element.

• If the segment contains more than one element:

  • Find the middle position:

  mid = floor((left + right) / 2)

  • Split the segment into two parts:
  • Left part: [left, mid]

  • Right part: [mid + 1, right]

  • The value of the current segment is the value of the left part minus the value of the right part.

Your task is to find and print the final value of the whole array.

Input

The first line contains one positive integer n
1 ≤ n ≤ 10^5

The second line contains n integers:

a0, a1, ..., a(n-1)

where:

-10^9 ≤ ai ≤ 10^9

Output

Print one integer, the final divide and conquer subtraction value.

Example

Input

8
10 3 2 1 8 4 7 5

Output

4

Explanation

The whole array is the segment [0, 7].

First, split it into two parts:

[0, 3] and [4, 7]

The value of the left part is:

(10 - 3) - (2 - 1) = 6

The value of the right part is:

(8 - 4) - (7 - 5) = 2

Therefore, the value of the whole array is:

6 - 2 = 4

So the final answer is 4.

Constraints

• 1 ≤ n ≤ 10^5
• -10^9 ≤ ai ≤ 10^9