（最大值之和）给定整数序列 $a_0,\cdots,a_{n-1}$，求该序列所有非空连续子序列的最大值之和。上述参数满足 $1\le n\le 10^5$ 和 $1\le a_i\le 10^8$。

一个序列的非空连续子序列可以用两个下标 $l$ 和 $r$（其中$0 \le l \le r < n$）表示，对应的序列为 $a_l,a_{l+1},\cdots,a_r$。两个非空连续子序列不同，当且仅当下标不同。

例如，当原序列为 $[1,2,1,2]$ 时，要计算子序列 $[1]$、$[2]$、$[1]$、$[2]$、$[1,2]$、$[2,1]$、$[1,2]$、$[1,2,1]$、$[2,1,2]$、$[1,2,1,2]$ 的最大值之和，答案为 $18$。注意 $[1,1]$ 和 $[2,2]$ 虽然是原序列的子序列，但不是连续子序列，所以不应该被计算。另外，注意其中有一些值相同的子序列，但由于他们在原序列中的下标不同，属于不同的非空连续子序列，所以会被分别计算。

解决该问题有许多算法，以下程序使用分治算法，时间复杂度 $O(n\log n)$。

试补全程序。

1#include <iostream>2#include <algorithm>3#include <vector>4 5const int MAXN = 100000;6 7int n;8int a[MAXN];9long long ans;10 11void solve(int l, int r) {12    if (l + 1 == r) {13        ans += a[l];14        return;15    }16    int mid = (l + r) >> 1;17    std::vector<int> pre(a + mid, a + r);18    for (int i = 1; i < r - mid; ++i) ①;19    std::vector<long long> sum(r - mid + 1);20    for (int i = 0; i < r - mid; ++i)21        sum[i + 1] = sum[i] + pre[i];22    for (int i = mid - 1, j = mid, max = 0; i >= l; --i) {23        while (j < r && ②) ++j;24        max = std::max(max, a[i]);25        ans += ③;26        ans += ④;27    }28    solve(l, mid);29    solve(mid, r);30}31 32int main() {33    std::cin >> n;34    for (int i = 0; i < n; ++i)35        std::cin >> a[i];36    ⑤;37    std::cout << ans << std::endl;38    return 0;39}