20799번 - Rikka with Maximum Subsegment Sum 다국어

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$.