WA 100悬棺求条

#include <bits/stdc++.h>
#define int long long
using namespace std;

namespace ds {
	struct fhqNode {
		int num, key;
		int sz, cnt;
		fhqNode *l, *r;
		fhqNode(int v) : num(v), key(rand()), sz(1), cnt(1), l(nullptr), r(nullptr) {}
	};
#define num(x) (x)->num
#define prio(x) (x)->key
#define cnt(x) (x)->cnt
#define lc(x) (x)->l
#define rc(x) (x)->r
#define sz(x) ((x) ? (x)->sz : 0)
#define upd_sz(x) if(x) (x)->sz = sz(lc(x)) + sz(rc(x)) + cnt(x)
	
	pair<fhqNode*, fhqNode*> __fhqtreap_split(fhqNode* p, int val) {
		if (!p)
			return {nullptr, nullptr};
		if (num(p) <= val) {
			auto [lr, rr] = __fhqtreap_split(rc(p), val);
			rc(p) = lr;
			upd_sz(p);
			return {p, rr};
		} else {
			auto [lr, rr] = __fhqtreap_split(lc(p), val);
			lc(p) = rr;
			upd_sz(p);
			return {lr, p};
		}
	}
	
	fhqNode* __fhqtreap_merge(fhqNode *p, fhqNode *q) {
		if (!p) return q;
		if (!q) return p;
		if (prio(p) > prio(q)) {
			rc(p) = __fhqtreap_merge(rc(p), q);
			upd_sz(p);
			return p;
		} else {
			lc(q) = __fhqtreap_merge(p, lc(q));
			upd_sz(q);
			return q;
		}
	}
	
	fhqNode* __fhqtreap_insert(fhqNode* root, int val) {
		auto [lft, rht] = __fhqtreap_split(root, val);
		auto [mid_left, mid] = __fhqtreap_split(lft, val - 1);
		
		if (mid) {
			cnt(mid)++;
			upd_sz(mid);
			root = __fhqtreap_merge(__fhqtreap_merge(mid_left, mid), rht);
		} else {
			fhqNode* newNode = new fhqNode(val);
			root = __fhqtreap_merge(__fhqtreap_merge(mid_left, newNode), rht);
		}
		return root;
	}
	
	fhqNode* __fhqtreap_remove(fhqNode* root, int val) {
		auto [lft, rht] = __fhqtreap_split(root, val);
		auto [mid_left, mid] = __fhqtreap_split(lft, val - 1);
		
		if (mid) {
			if (cnt(mid) > 1) {
				cnt(mid)--;
				upd_sz(mid);
				root = __fhqtreap_merge(__fhqtreap_merge(mid_left, mid), rht);
			} else {
				delete mid;
				mid = nullptr;
				root = __fhqtreap_merge(mid_left, rht);
			}
		} else {
			root = __fhqtreap_merge(__fhqtreap_merge(mid_left, mid), rht);
		}
		return root;
	}
	
	bool __fhqtreap_contains(fhqNode* root, int val) {
		if (!root) return false;
		if (num(root) == val) return true;
		if (num(root) > val) return __fhqtreap_contains(lc(root), val);
		return __fhqtreap_contains(rc(root), val);
	}
	
	int __fhqtreap_kth(fhqNode* root, int k) {
		if (!root || k < 1 || k > sz(root)) return -1;
		int lftsz = sz(lc(root));
		if (k <= lftsz) return __fhqtreap_kth(lc(root), k);
		if (k <= lftsz + cnt(root)) return num(root);
		return __fhqtreap_kth(rc(root), k - lftsz - cnt(root));
	}
	
	int __fhqtreap_rank(fhqNode* root, int val) {
		if (!root) return 0;
		if (num(root) >= val) return __fhqtreap_rank(lc(root), val);
		return sz(lc(root)) + cnt(root) + __fhqtreap_rank(rc(root), val);
	}
	
	int __fhqtreap_upper_bound(fhqNode* root, int val) {
		auto [lft, rht] = __fhqtreap_split(root, val);
		int result = -1;
		if (rht) {
			fhqNode* cur = rht;
			while (cur && lc(cur)) cur = lc(cur);
			if (cur) result = num(cur);
		}
		root = __fhqtreap_merge(lft, rht);
		return result;
	}
	
	int __fhqtreap_lower_bound(fhqNode* root, int val) {
		auto [lft, rht] = __fhqtreap_split(root, val - 1);
		int result = -1;
		if (rht) {
			fhqNode* cur = rht;
			while (cur && lc(cur)) cur = lc(cur);
			if (cur) result = num(cur);
		}
		root = __fhqtreap_merge(lft, rht);
		return result;
	}
	
	int __fhqtreap_predecessor(fhqNode* root, int val) {
		auto [lft, rht] = __fhqtreap_split(root, val - 1);
		int result = INT32_MAX;
		if (lft) {
			fhqNode* cur = lft;
			while (cur && rc(cur)) cur = rc(cur);
			if (cur) result = num(cur);
		}
		root = __fhqtreap_merge(lft, rht);
		return result;
	}
	
	int __fhqtreap_successor(fhqNode* root, int val) {
		auto [lft, rht] = __fhqtreap_split(root, val);
		int result = -INT32_MAX;
		if (rht) {
			fhqNode* cur = rht;
			while (cur && lc(cur)) cur = lc(cur);
			if (cur) result = num(cur);
		}
		root = __fhqtreap_merge(lft, rht);
		return result;
	}
	
	void __fhqtreap_inorder(fhqNode* root) {
		if (!root) return;
		__fhqtreap_inorder(lc(root));
		for (int i = 0; i < cnt(root); i++)
			cout << num(root) << " ";
		__fhqtreap_inorder(rc(root));
	}
	
	void __fhqtreap_clear(fhqNode* root) {
		if (!root) return;
		__fhqtreap_clear(lc(root));
		__fhqtreap_clear(rc(root));
		delete root;
	}
	
#undef num
#undef prio
#undef cnt
#undef lc
#undef rc
#undef sz
#undef upd_sz
}

int n, ans;
map<int, int> __cnt;
using namespace ds;

signed main() {
	cin >> n;
	srand(time(0));
	fhqNode* root = nullptr;
	
	if (n == 1) {
		int k;
		cin >> k;
		cout << k << '\n';
		return 0;
	}
	
	for (int i = 1; i <= n; i++) {
		int v;
		cin >> v;
		int diff = INT_MAX;
		int pre  = __fhqtreap_predecessor(root, v);
		int suc = __fhqtreap_successor(root, v);
		if (pre != INT_MAX)
			diff = min(abs(pre-v), diff);
		if (suc != INT_MAX)
			diff = min(abs(suc-v), diff);
		if (diff == INT_MAX)
			diff = v;
//		cout << "_______===_______\n" 
//		<< diff 
//		<< "\n__________===____\n\n";
		ans += diff*(__cnt[v]<1);
		root = __fhqtreap_insert(root, v);
		__cnt[v]++;
	}
	cout << ans << '\n';
	
	return 0;
}