Maximum Building Height

You are given a series of building blocks, each with an integer height (which can be negative). Using these blocks in sequential order, your task is to construct a building by choosing a contiguous segment of blocks. The height of the building is defined as the sum of the heights of the chosen blocks, i.e., ( S = \sum_{i=l}^{r} a_i ), where ( l ) and ( r ) are the starting and ending indices of the segment. Note that if the blocks have negative values, they may reduce the overall sum, and in the case where all blocks are negative, the answer is the maximum (least negative) block value. Your program should compute the maximum possible building height based on the given blocks.

inputFormat

The first line of input contains a single integer ( n ) representing the number of building blocks. The second line contains ( n ) space-separated integers representing the heights of the building blocks.

outputFormat

Output a single integer, which is the maximum possible height of a building that can be constructed using a contiguous segment of the given blocks.## sample

7
1 2 3 4 5 6 7

28