记录编号	563218	评测结果	AAAAAAAAAA
题目名称	[BJOI 2011]双端队列	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.577 s
提交时间	2021-07-19 12:07:49	内存使用	4.60 MiB

#include <cstdio>
#include <algorithm>
#include <set>
using namespace std;

const int N = 2e5 + 10;
int n, m, a[N], v[N], Left[N], Right[N];
set<int> S;

int main()
{
	freopen("bjoi2011_deque.in", "r", stdin);
	freopen("bjoi2011_deque.out", "w", stdout);
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i)
	{
		scanf("%d", a + i);
		S.insert(a[i]);
	}
	for (int x: S) v[++m] = x;
	for (int i = 1; i <= n; ++i)
	{
		a[i] = lower_bound(v + 1, v + m + 1, a[i]) - v;
		Right[a[i]] = i;
		if (!Left[a[i]]) Left[a[i]] = i;
	}
	int weight = 1, ans = 0;
	while (weight <= m)
	{
		int L = Left[weight], R = 0;
		while (weight < m)
		{
			if (R > Left[weight + 1]) break;
			++weight;
			if (Right[weight] > L) R = max(R, Right[weight]);
			L = min(L, Left[weight]);
		}
		weight += 1;
		ans += 1;
	}
	printf("%d\n", ans);
	return 0;
}