（最大值之和） 给定整数序列 a0...an-1，求该序列所有非空连续子序列的最大值之和。上述参数满足1<=n<=10^5 和 1<=ai<=10^8 一个序列的非空连续子序列可以用两个下标l和r(其中0 <=l<=r<=n)表示，对应的序列为al,al+1,...ar。两个非空连续子序列不同，当且仅当下标不同。 例如，当原序列为[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(nlogn)。 试补全程序

#include <iostream>
#include<algorithm>
#include <vector>

const int MAXN = 100000;

int n;
int a[MAXN];
long long ans;

void solve(int l, int r) {
	if(l+1==r) {
		ans += a[l];
		return;
	}
	int mid=(l+r)>>1;
	std::vector<int> pre(a + mid,a+r);
	for (int i=l; i<r-mid; ++i)   __(1)__ ;
		std::vector<long long> sum(r - mid + 1);
	for (int i=0; i<r-mid; ++i) sum[i+1]= sum[i]+ pre[i];
	for (int i=mid-1,j=mid,max = 0; i>= l; --i) {
		while (j<r &&  __(2)__ ) ++j;
		max = std::max(max,a[i]);
		ans += __(3)__;
		ans += __(4)__;
	}
	solve(l, mid);
	solve(mid, r);
}

int main() {
	std::cin >> n;
	for (int i=0; i<n; ++i) std::cin >> a[i];
	__(5)__ ;
	std::cout << ans << std::endl;
	return 0;
}