Search for the maximum sum of a subarray with permutations

C# Medium arrays

Task «Search for the maximum sum of a subarray with permutations»

Given an array of integers. You are allowed to perform at most one operation: choose two elements of the array and swap them. Find the maximum possible sum of a contiguous subarray (of any length, including 0) after performing at most one swap. If the sum can be negative, output 0. The length of the array is from 1 to 10^5, elements are from -10^4 to 10^4.

Input Format

The first line contains an integer N — the number of elements in the array. The second line contains N integers separated by spaces.

Output Format

One integer — the maximum sum of the subarray.

Examples

Example 1

INPUT

3
-1 -2 -3

OUTPUT

0

Example 2

INPUT

5
1 2 3 4 5

OUTPUT

15

Example 3

INPUT

4
-1 2 3 -4

OUTPUT

5

main.cs