Given an array $A$ of $n$ elements. Choose two non-overlapping, non-empty subarrays of $A$ such that their sum is maximized. In other words, find four indices $1 \le l \le r < i \le j \le n$ such that $(A_l + A_{l + 1} + ... + A_r) + (A_i + A_{i + 1} + ... + A_j)$ is maximized.
### Input
- The first line contains an integer $n$.
- The second line contains $n$ integers $A_i$.
### Output
- Print an integer, the maximum sum.
### Constraints
- $1 \le n \le 10^5$.
- $0 \le |A_i| \le 10^9$.
### Example
Input:
```
5
3 -2 8 -1 2
```
Output:
```
12
```
