# Segment tree (+) from operator import add from itertools import accumulate class SegmentTree: _f = None _data = None _offset = None _size = None def __init__(self, size, f): self._f = f self._size = size t = 1 while t < size: t *= 2 self._offset = t - 1 self._data = [0] * (t * 2 - 1) def update_all(self, iterable): data = self._data data[self._offset:self._offset + self._size] = iterable for i in range(self._offset - 1, -1, -1): data[i] = data[i * 2 + 1] + data[i * 2 + 2] def query(self, start, stop): def iter_segments(data, l, r): while l < r: if l & 1 == 0: yield data[l] if r & 1 == 0: yield data[r - 1] l = l // 2 r = (r - 1) // 2 f = self._f it = iter_segments(self._data, start + self._offset, stop + self._offset) result = next(it) for e in it: result = f(result, e) return result N, *A = map(int, open(0).read().split()) a = list(accumulate(A)) st = SegmentTree(N, add) st.update_all(a) result = 0 result += st.query(0, N) for i in range(1, N): result += st.query(i, N) - a[i - 1] * (N - i) print(result)