Maximum Magical Power

You are given an array of integers representing the magical power of fruits. Your task is to find the maximum magical power that can be obtained from any contiguous subarray. Formally, given an array (a_1, a_2, \ldots, a_n), compute the value

[ \max_{1 \leq i \leq j \leq n} \sum_{k=i}^{j} a_k ]

using an optimal algorithm.

inputFormat

The input is read from standard input (stdin). The first line contains a single integer (n) which represents the number of fruits. The second line contains (n) space-separated integers, where each integer represents the magical power of a fruit.

outputFormat

Output to standard output (stdout) a single integer — the maximum magical power that can be obtained from any contiguous subarray of the given list.## sample

6
1 -2 3 4 -1 5

11