Maximum Cash Collection

You are given a queue of people, where each person carries a certain amount of cash. The amounts can be positive, negative, or zero. Your task is to determine the maximum amount of cash that can be collected from any contiguous block of people in the queue.

This problem can be solved using Kadane's algorithm. The algorithm iterates through the list of cash values, at each step updating the maximum contiguous sum ending at that position, and then the global maximum. The formula for updating the current sum is given by:

\( current\_sum = \max(a_i, current\_sum + a_i) \)

and the overall maximum is updated as:

\( max\_so\_far = \max(max\_so\_far, current\_sum) \)

Good luck!

inputFormat

The first line of input contains a single integer \( n \) representing the number of people in the queue.

The second line contains \( n \) space-separated integers, where each integer represents the amount of cash that the \( i^{th} \) person has. The cash amounts may be negative, zero, or positive.

outputFormat

Output a single integer, which is the maximum sum of cash that can be collected from any contiguous subsequence of people in the queue.

## sample

5
1 2 3 4 5

15

</p>