Given an array $A$ of length $N$, your task is divide array into two non-empty subarray such that each of element present in the array must belong to exactly one subarray and the Good value is defined as the absolute difference between sum of both subarrays ( Let a be the sum of first subarray and b be the sum of second subarray , therefore it's Good Value is $abs(a-b)$ ). Your task is to find the minimum possible Good Value of array $A$.

 Input Format

The first line contains $N$, the size of array $A$

The second line contains $N$ space seperated integers, the elements of $A$

Output Format

Output minimum Good Value possible for array $A$ 

Constraints

$2 \leq N \leq 2 \times 10^5$

$1 \leq A[i] \leq 10^5$