Submission #1136340

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

vector<int> a[100010];

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	int amax = 0;
	for (int i = 0; i < n; i++) {
		int x;
		cin >> x;
		a[x].push_back(i);
		amax = max(amax, x);
	}
	int ans = 1, cur = -1;
	for (int i = 1; i <= amax; i++) {
		if (a[i].empty()) continue;
		int idx = upper_bound(a[i].begin(), a[i].end(), cur) - a[i].begin();
		if (idx == 0) {
			cur = a[i].back();
			continue;
		}
		cur = a[i][idx - 1];
		if (cur != 0 || i != amax) ans++;
	}
	cout << ans << endl;
	return 0;
}

Submission Info

Judge Result