Competitions

# December 4 - BMTK Programming School, High League

# Thylacine

Given the sequence of **n** integers. Find its nonempty subsequence of consecutive numbers, such that the sum of these numbers is maximal.

#### Input

First line contains number **n** (**1** ≤ **n** ≤ `10`

). Second line contains the sequence elements, each of them is no more than ^{6}**1000**.

#### Output

Print the maximum sum of numbers in non-empty sub-sequence of consecutive numbers.

Input example #1

6 4 2 3 -7 8 1

Output example #1

11

Input example #2

8 2 -1 4 3 -8 6 -3 4

Output example #2

8

Input example #3

3 -12 -6 -1

Output example #3

-1