Maximum Sum Subarray with Divide & Conquer Algorithm

Given an array of n integers, find a contiguous subarray with the maximum sum of values using the divide & conquer technique.

Input

The first line of the input contains an integer n - number of elements in the array (1 ≤ n ≤ ).
The next line contains n integers separated by a space, that represent the elements of the array .

Output

The program should print a single integer - the highest possible sum of the subarrays in the given array.

Examples

Input
Output
9 -2 1 -3 4 -1 3 1 -4 -2
7
10 1 -2 3 4 -3 1 7 -10 -20 4
12

Explanation

  1. -2 1 -3 4 -1 3 1 -4 -2 → The sum of the highlighted subarray is (4 - 1 + 3 + 1) = 7
  1. 1 -2 3 4 -3 1 7 -10 -20 4 → 3 + 4 -3 + 1 + 7 = 12
 

Constraints

Time limit: 5 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in