Given an array $A$ of $n$ elements. Choose three non-overlapping, non-empty subarrays of $A$ such that their sum is maximized. In other words, find six indices $1 \le l \le r < i \le j < p \le k \le n$ such that $(A_l + A_{l + 1} + ... + A_r) + (A_i + A_{i + 1} + ... + A_j) + (A_p + A_{p + 1} + ... + A_k)$ 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:
```
13
```
