Rikka와 최대 부분 구간 합

Maximum Subsegment Sum은 고전적인 문제다. Rikka는 이 문제를 처음 봤을 때만 해도 competitive programming의 외부인이었지만, 지금은 이 대회의 출제자가 되었다.

Rikka는 Maximum Subsegment Sum에 관한 문제를 내기로 했다. 길이가 $m$인 배열 $x$가 주어졌을 때, 최대 부분 구간 합은 다음과 같이 정의한다. $\operatorname{mss}(A) = \max_{1\leq i \leq j \leq m} \left(\sum_{k=i}^j x_k \right).$

이제 길이가 $n$인 정수 배열 $A$가 주어진다. Rikka는 $A$의 모든 부분 구간에 대한 최대 부분 구간 합을 구해 더한 값을 원한다. $\sum_{1 \leq i \leq j \leq n} \operatorname{mss}([A_i, \dots, A_j]).$

첫째 줄에 정수 $n$($1 \leq n \leq 10^5$)이 주어진다.

둘째 줄에 정수 $n$개 $A_i$($-10^9 \leq A_i \leq 10^9$)가 주어진다.

답이 매우 클 수 있으므로, 답을 $2^{64}$로 나눈 나머지를 한 줄에 정수 하나로 출력한다. 답을 $x$라고 할 때, $y = x + k \times 2^{64}$를 만족하는 정수 $k$가 존재하는 가장 작은 음이 아닌 정수 $y$를 출력한다.