Smallest Sum Subarray

You are given an array of integers. Your task is to find the smallest sum of a contiguous subarray within the given array. In other words, you must select a subarray (i.e. a contiguous segment) whose sum is as small as possible.

This problem is a variation of the classic maximum subarray problem and can be solved using a modified version of Kadane's algorithm. Mathematically, if the array is given as (a_1, a_2, \dots, a_n), you need to compute (min_{1 \leq i \leq j \leq n} \sum_{k=i}^{j} a_k).

inputFormat

The first line contains an integer (n) representing the number of elements in the array. The second line contains (n) space-separated integers representing the elements of the array.

outputFormat

Output a single integer which is the smallest sum that can be obtained from any contiguous subarray.## sample

7
3 -4 2 -3 -1 7 -5

-6