Description：

每次 $reduce(i)$ 操作可以把 $a[i]$ 和 $a[i+1]$ 合并，代价为两个的较大值，问最少的代价把整个序列合成一个。

$1\leqslant n\leqslant 10^6$

Solution：

神奇的单调栈，发现肯定我们要尽量不让大的和别人合并次数太多，我们考虑两个元素 $a[i]$ 和 $a[j]$ ，如果中间有一个数比他们都大，那么一定会产生最大的那个数的贡献，否则把他们用 $\max(a[i],a[j])$ 合并最优，然后题解用了一个很神奇的单调栈，就是维护一个单调递减的栈，如果当前这个数小于栈顶，那就直接把他加进去，否则要把栈顶弹掉，这时这个左右两边第一个比它大的都已经出现，那么这个数字是不能与这之外的产生贡献的，那么就把这个和两个之中较小的合并即可，最后栈里还会剩一些，就从小到大顺次合并即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n;

#define MAXN 1000010

int a[MAXN];

int s[MAXN],top = 0;

int main()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)scanf("%d",&a[i]);

	long long ans = 0;

	for(int i = 1;i <= n;++i)

	{

		while(top > 0 && a[s[top]] <= a[i])

		{

			--top;

			if(top > 0 && a[s[top]] <= a[i])ans += a[s[top]];

			else ans += a[i];

		}

		s[++top] = i;

	}

	for(int i = 1;i < top;++i)

	{

		ans += a[s[i]];

	}

	cout << ans << endl;

	return 0;

}