Balanced Tug of War

In this problem, you are given an array \(a_1, a_2, \dots, a_n\) representing the strength values of \(n\) students. You need to form two teams for a tug of war. Each team is chosen as a contiguous subarray, and the two subarrays must not overlap. Formally, if the first team is represented by \(a_{l_1}, a_{l_1+1}, \dots, a_{r_1}\) and the second team by \(a_{l_2}, a_{l_2+1}, \dots, a_{r_2}\), then they must satisfy

\(1 \le l_1 \le r_1 < l_2 \le r_2 \le n\).

The goal is to choose two subarrays so that the absolute difference between the sum of strengths of the two teams is minimized. That is, if \(S_1\) and \(S_2\) are the sums for the first and second teams respectively, you need to minimize \(|S_1 - S_2|\). Output the minimum possible difference.

inputFormat

The first line contains an integer \(n\) (\(2 \le n\)) denoting the number of students.

The second line contains \(n\) space-separated integers \(a_1, a_2, \dots, a_n\) representing the strength values of the students.

outputFormat

Output a single integer, which is the minimum absolute difference \(|S_1 - S_2|\) between the sums of the two teams.

sample

4
1 3 2 4

1