Artem and Array CodeForces - 442C (贪心)

#include <iostream>
#include <algorithm>
#include <math.h>
#include <cstdio>
#include <vector>
#include <string.h>
#include <queue>
#define PER(i,a,n) for(int i=n;i>=a;--i)
#define REP(i,a,n) for(int i=a;i<=n;++i)

using namespace std;

const int N = 2e6+10;
int a[N], b[N], f[N], n, m, k;
int q[N];

int main() {
	scanf("%d", &n);
	REP(i,1,n) scanf("%d", a+i);
	ll ans = 0;
	REP(i,1,n) {
		while (*q>1&&q[*q]<=a[i]&&q[*q]<=q[*q-1]) {
			ans += min(q[--*q], a[i]);
		}
		q[++*q] = a[i];
	}
	sort(q+1,q+1+*q);
	REP(i,1,*q-2) ans += q[i];
	printf("%I64d\n", ans);
}