Maximum Milk Production

You are given the milk production capacities of n cows arranged in a line. Each cow produces milk with a certain capacity which can be negative (indicating a loss) or positive (indicating a gain). Your task is to find the maximum sum of milk production capacities from any contiguous subarray. Formally, given an array (A) of length (n), you need to compute the value [ \max_{1 \leq i \leq j \leq n} \sum_{k=i}^{j} A_k ] using an efficient algorithm. This is a classic problem that can be solved in (O(n)) time using Kadane's algorithm.

inputFormat

The input is given via standard input (stdin) and consists of two lines. The first line contains a single integer (n) ((1 \le n \le 10^6)), the number of cows. The second line contains (n) space-separated integers representing the milk production capacities of the cows. The capacities can be negative or positive.

outputFormat

Output a single integer to standard output (stdout) – the maximum sum of milk production capacities of any contiguous subarray.## sample

9
-2 1 -3 4 -1 2 1 -5 4

6