Minimum Final Element

Given a sequence of n integers \(a_1, a_2, \ldots, a_n\), you are allowed to perform a sequence of operations in which you replace two adjacent numbers \(x\) and \(y\) with \(x - y\). When these operations are performed optimally, it can be proven that the minimum possible value of the final (single) element is:

• \(0\) if \(n\) is even,
• \(\min\{a_1, a_2, \ldots, a_n\}\) if \(n\) is odd.

Your task is to write a program that reads the integer sequence from standard input and outputs the minimum possible final element to standard output.

Note: The proof of the optimal strategy is not required; you just need to implement the above observation.

inputFormat

The input is given via standard input. The first line contains an integer \(n\) (\(1 \le n \le 10^5\)) representing the number of elements. The second line contains \(n\) space-separated integers \(a_1, a_2, \ldots, a_n\) (each with an absolute value up to \(10^9\)).

outputFormat

Output a single integer --- the minimum possible value of the final element after performing the allowed operations optimally.

4
1 2 3 4

0