Submission #67784688

---

Source Code Expand

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

using namespace std;

inline int nxt() {
	int x;
	cin >> x;
	return x;
}

void reduce(vector<int>& cur) {
	while ((int)cur.size() >= 2) {
		int x = cur.back();
		if (*(cur.end() - 2) == x) {
			cur.pop_back();
			cur.back() += 1;
		} else {
			break;
		}
	}
}

void solve() {
	int n = nxt();
	long long ans = 0;
	vector<int> cur;
	for (int i = 0; i < n; ++i) {
		int x = nxt();
		while (!cur.empty() && cur.back() < x) {
			int y = cur.back();
			cur.pop_back();
			int mn = x;
			if (!cur.empty() && cur.back() < mn) {
				mn = cur.back();
			}
			ans += mn - y;
			cur.push_back(mn);
			reduce(cur);
		}
		cur.push_back(x);
		reduce(cur);
	}
	if ((int)cur.size() > 1) {
		ans += cur[0] - cur.back() - (int)cur.size() + 2;
	}
	cout << ans << "\n";
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int t = nxt();
	while (t--) {
		solve();
	}

	return 0;
}

Submission Info

Judge Result