Closest Sums of Contiguous Subarrays

You are given an array of integers A with length n. Your task is to find the index i (with 1 ≤ i < n) so that if the array is split into two contiguous non-empty parts, the absolute difference between the sum of the first part and the sum of the second part is minimized.

More formally, if we denote the two parts as:

• \( S_L = \sum_{k=1}^{i} a_k \)
• \( S_R = \sum_{k=i+1}^{n} a_k \)

you are required to output S_L and S_R such that \(|S_L - S_R|\) is as small as possible. It is guaranteed that the array will have at least two elements.

Example: For the array [1, 2, 3, 4, 5], one optimal solution is to split after the third element yielding \(S_L = 1+2+3 = 6\) and \(S_R = 4+5 = 9\) with an absolute difference of 3.

inputFormat

The input is read from standard input and consists of two lines:

• The first line contains an integer n (2 ≤ n ≤ 10⁵), the number of elements in the array.
• The second line contains n space-separated integers representing the array elements.

outputFormat

Output to standard output two space-separated integers representing the sums of the two contiguous subarrays (\(S_L\) and \(S_R\)) that yield the minimal absolute difference.

5
1 2 3 4 5

6 9