最大子数组和（含重排操作）

Swift Hard arrays

任务 «最大子数组和（含重排操作）»

给定一个整数数组。允许执行最多一次操作：选择任意一个子数组，并任意重新排列其中的元素。求执行此操作后（或不执行操作）任意连续子数组的最大可能和。数组可能包含负数。限制条件：数组长度不超过 10^5，元素范围从 -10^9 到 10^9。

第一行：整数 n (1 ≤ n ≤ 10^5) — 数组的长度。第二行：n 个以空格分隔的整数 — 数组的元素。

一个整数——经过最多一次重排后的子数组最大和。

输入

5
1 -2 3 4 -5

输出

8

输入

4
-1 -2 -3 -4

输出

-1

输入

/tmp/testdir
*.txt

输出

/tmp/testdir/subdir/file1.txt a1b2c3d4e5f6...
/tmp/testdir/file2.txt 1234567890abcdef...

输入

Hello World

输出

3

输入

3
5 -1 3

输出

8

main.swift