90分求调

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 4e5 + 5;
const int INF = 0x3f3f3f3f;
struct Node
{
	int id, val;
	bool operator <(const Node &other)const
	{
		return val < other.val;
	}
}a[MAXN];
int n;
int ans;
stack <int> st_pov;
stack <int> st_nega;
int pov[MAXN];
int nega[MAXN];
int b[MAXN];

void solve()
{
	b[0] = 0;
	for(int i = 1; i <= n; ++i)
	{
		if(st_pov.empty())
		{
			st_pov.push(a[i].id);
			continue;
		} 
		if(a[i].id > st_pov.top())
		{
			st_pov.push(a[i].id);
			continue;
		}
		while(a[i].id < st_pov.top())
		{
			pov[st_pov.top()] = a[i].id;
			st_pov.pop();
			if(st_pov.empty()) break;
		}
		st_pov.push(a[i].id);
	}

	for(int i = n; i >= 1; --i)
	{
		if(st_nega.empty())
		{
			st_nega.push(a[i].id);
			continue;
		} 
		if(a[i].id > st_nega.top())
		{
			st_nega.push(a[i].id);
			continue;
		}
		while(a[i].id < st_nega.top())
		{
			nega[st_nega.top()] = a[i].id;
			st_nega.pop();
			if(st_nega.empty()) break;
		}
		st_nega.push(a[i].id);
	}
	
	for(int i = 1; i <= n; ++i)
	{
		int minn = b[pov[a[i].id]];
		int maxn = b[nega[a[i].id]];
		if(minn == 0 && maxn == 0)
		{
			ans += a[i].val;
			continue;
		}
		minn = (minn == 0 ? INF : minn);
		maxn = (maxn == 0 ? -INF : maxn);
		minn -= a[i].val;
		maxn -= a[i].val;
		ans += min(abs(maxn), abs(minn));
	}
}

int main()
{
	cin >> n;
	for(int i = 1; i <= n; ++i)
	{
		scanf("%d", &a[i].val);
		a[i].id = i;
		b[i] = a[i].val;
	}
	sort(a + 1, a + 1 + n);
	solve();
	cout << ans;
	return 0;
}