Minimize Maximum Calorie Intake

You are given a chocolate bar that is divided into several segments. Each segment has an integer number of calories. Your task is to break the chocolate bar into exactly two pieces such that each piece contains at least one segment. After breaking the bar, you will eat the piece with the higher total calorie count. To control your calorie intake, you want to choose the break position so that the calorie count of the piece you eat is minimized.

Formally, given an array \(\textbf{calories} = [c_1, c_2, \dots, c_n]\) of positive integers, you need to find an index \(i\) (with \(1 \leq i < n\)) that minimizes \(\max\left(\sum_{j=1}^{i} c_j,\; \sum_{j=i+1}^{n} c_j\right)\). Print the minimum possible value of this maximum sum.

Input Format: The first line contains an integer \(n\) denoting the number of segments. The second line contains \(n\) space-separated integers representing the calorie counts of the segments.

Output Format: Print a single integer representing the minimum possible value of the maximum calories between the two pieces.

inputFormat

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

1. The first line contains an integer \(n\) (\(2 \leq n \leq 10^5\)), the number of segments.
2. The second line contains \(n\) space-separated integers \(c_1, c_2, \dots, c_n\) where each \(c_i\) (\(1 \leq c_i \leq 10^4\)) represents the number of calories in the \(i\)-th segment.

outputFormat

Output a single integer representing the minimum possible maximum number of calories between the two pieces of the chocolate bar after an optimal break.

4
4 5 9 7

16