Optimized Partitioning for Hiking Trails

Three friends are planning to hike a series of trails where each trail has a specified length. They want to divide the trails into three consecutive segments such that the maximum total distance assigned to any friend is minimized. In other words, if the trails are partitioned into three contiguous parts, determine the smallest possible value of the largest sum among these parts.

Formally, given an integer (N) representing the number of trails and a list of (N) positive integers ({a_1, a_2, \dots, a_N}), partition the list into at most three contiguous segments. Let (S_1), (S_2), and (S_3) be the sums of the segments. The goal is to minimize (\max(S_1, S_2, S_3)).

inputFormat

The input is read from standard input and consists of two lines. The first line contains an integer (N) ((1 \le N \le 10^5)) representing the number of trails. The second line contains (N) space-separated positive integers, where each integer represents the length of a trail.

outputFormat

Output a single integer to standard output, which is the minimized maximum distance any of the three friends would have to hike while dividing the trails optimally.## sample

7
4 3 6 8 10 2 7

18