Minimize Maximum Sum of Three Subarrays

Given an array of integers, you need to split it into three contiguous non-empty subarrays. Let the sums of the three subarrays be defined as follows:

$$S_1 = \sum_{k=1}^{i} a_k, \quad S_2 = \sum_{k=i+1}^{j} a_k, \quad S_3 = \sum_{k=j+1}^{n} a_k, \quad \text{with } 1 \le i < j < n.$$

Your task is to choose two indices i and j to partition the array such that the value $$\max(S_1, S_2, S_3)$$ is minimized. In other words, find the splitting that minimizes the maximum sum among the three subarrays.

Note: The subarrays must be contiguous and non-empty.

inputFormat

The input is given via stdin and consists of two lines:

• The first line contains an integer n (with n ≥ 3) representing the number of elements in the array.
• The second line contains n space-separated integers representing the array elements.

outputFormat

Output a single integer to stdout — the minimum possible maximum sum among the three contiguous subarrays.

6
1 2 3 4 5 6

9