Problem Description

Xiaoming is a teacher at a school. There are $n$ students in his class, and the strength value of the $i$-th student is $a_i$. In his free time, Xiaoming decides to organize a tug-of-war contest in the class.

To make the two sides as evenly matched as possible, he needs to choose two teams from these $n$ students. The students in each team must have consecutive indices: $\{{a_{l_1}}, a_{l_1 + 1}, \dots, a_{r_1 - 1}, a_{r_1}\}$ and $\{{a_{l_2}}, a_{l_2 + 1}, \dots, a_{r_2 - 1}, a_{r_2}\}$, where $l_1 \le r_1 < l_2 \le r_2$.

The two teams do not have to have the same number of students, but the sums of the strength values within the two teams should be as close as possible. Please compute the minimum possible difference between the sums of strength values among all valid ways to pick the two teams.

Input Format

The input has two lines.
The first line contains a positive integer $n$.
The second line contains $n$ positive integers $a_1, a_2, \dots, a_n$.

Output Format

Output one line containing a non-negative integer, representing the minimum difference between the sums of strength values of the two teams.

5
10 9 8 12 14

1

Hint

Sample 1 Explanation

One optimal selection is:

Team $1$: $\{a_1, a_2, a_3\}$, Team $2$: $\{a_4, a_5\}$. The sums of strength values are $10 + 9 + 8 = 27$ and $12 + 14 = 26$, so the difference is $|27 − 26| = 1$.

Constraints

• For $20\%$ of the testdata, $n \leq 50$.
• For all testdata, it is guaranteed that $2 \leq n \leq 10^3$ and $1 \leq a_i \leq 10^9$.

Translated by ChatGPT 5