시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 512 MB 0 0 0 0.000%

문제

Maximum Subsegment Sum is a classical problem. When Rikka first saw this problem, she was still an outsider of competitive programming, and now, she has become a problem setter of this grand event.

Therefore, Rikka decides to set a problem about Maximum Subsegment Sum. Given an array $x$ of length $m$, its maximum subsegment sum $\operatorname{mss}(A)$ is defined as: $$\operatorname{mss}(A) = \max_{1\leq i \leq j \leq m} \left(\sum_{k=i}^j x_k \right) .$$

Now, given an integer array $A$ of length $n$, Rikka wants you to calculate the sum of the maximum subsegment sums of all subsegments of $A$, i.e. $$\sum_{1 \leq i \leq j \leq n} \operatorname{mss}([A_i, \dots, A_j]) .$$

입력

The first line contains a single integer $n\ (1 \leq n \leq 10^5)$.

The second line contains $n$ integers $A_i\ (-10^9 \leq A_i \leq 10^9)$.

출력

Output a single line with a single integer, the answer. The answer can be very large, therefore, you are only required to output the answer modulo $2^{64}$.

More formally, suppose the answer is $x$, you are required to find the smallest non-negative integer $y$ satisfying $y = x + k \times 2^{64}$ for some integer $k$.

예제 입력 1

5
1 -1 1 -1 1

예제 출력 1

11

예제 입력 2

5
1 -2 3 -4 5

예제 출력 2

39

예제 입력 3

10
1 -3 -5 7 -9 10 8 -6 -4 2

예제 출력 3

555

예제 입력 4

4
-1 -2 -3 -4

예제 출력 4

18446744073709551596