Minimize Maximum Cluster Sum

You are given a sequence of n non-negative integers representing distances between successive points. Your task is to partition the sequence into one or more contiguous clusters (subarrays) such that the maximum sum among all clusters is minimized.

Formally, let the distances be \(a_1, a_2, \dots, a_n\). We want to split the array into contiguous segments. For a given partition, let \(S_i\) denote the sum of distances in the i-th segment. Our goal is to find a partition that minimizes \(\max\{S_1, S_2, \dots, S_k\}\). It can be shown that if each element forms its own segment, the minimized maximum is \(\max\{a_i\}\). Therefore, the answer is always \(\max\{a_1, a_2, \dots, a_n\}\).

Note: Although the problem might seem trivial, you are required to implement it using a binary search strategy as described in the sample solution.

inputFormat

The input is provided via standard input (stdin) in the following format:

• The first line contains an integer n denoting the number of distances.
• The second line contains n space-separated non-negative integers representing the distances.

\(\textbf{Constraints:}\) n \ge 1 and each distance is between 0 and \(10^9\).

outputFormat

Output via standard output (stdout) a single integer: the minimized maximum sum among all clusters. In other words, output \(\max\{a_1, a_2, \dots, a_n\}\).

6
1 5 2 4 8 3

8