记录编号	317560	评测结果	AAAAAAAAAA
题目名称	[HZOI 2016]从零开始的序列	最终得分	100
用户昵称	Fmuckss	是否通过	通过
代码语言	C++	运行时间	0.354 s
提交时间	2016-10-08 09:43:04	内存使用	4.89 MiB

#include <iostream>
#include <cstdio>
#include <set>
#include <vector>
using namespace std;
const int maxn = 2e5 + 10;

struct Number {
	int v, id;
	Number() {}
	Number(int v_, int id_) { v = v_, id = id_; }
	
	bool operator < (const Number &b) const {
		return v == b.v ? id > b.id : v > b.v;
	}
};

int n, a[maxn], l[maxn], r[maxn];
vector <Number> del_que[maxn];
set <Number> now_que;

#define is_num(x) (x <= '9' and x >= '0')
inline int get_num() {
	char tmp = getchar();
	int res = 0;
	bool flag = false;
	
	while (not is_num(tmp)) {
		if (tmp == '-') flag = true;
		tmp = getchar();
	}
	
	while (    is_num(tmp)) {
		res = (res << 3) + (res << 1) + tmp - '0';
		tmp = getchar();
	}
	
	return res;
} 

inline void read() {
	n = get_num();
	for (int i = 1; i <= n; i++) a[i] = get_num();
}

inline void solve() {
	l[1] = 0, r[n] = n + 1;
	a[0] = a[n + 1] = 1000000;
	
	for (int i = 2; i <= n; i++) {
		l[i] = i - 1;
		while (a[l[i]] >= a[i] and l[i] > 0) l[i] = l[l[i]];
	}

	for (int i = n - 1; i >= 1; i--) {
		r[i] = i + 1;
		while (a[r[i]] >= a[i] and r[i] < n + 1) r[i] = r[r[i]];
	}
	
	for (int i = 1; i <= n; i++) {
		int len = r[i] - l[i] - 1;
		del_que[len].push_back(Number(a[i], i));
		now_que.insert(Number(a[i], i));
	}
	
	for (int i = 1; i <= n; i++) {
		printf("%d ", (*(now_que.begin())).v);
		for (int j = 0; j < del_que[i].size(); j++) now_que.erase(del_que[i][j]);
	}
}

int main() {
	freopen("sky_seq.in", "r", stdin);
	freopen("sky_seq.out", "w", stdout);
	read();
	solve();
	return 0;
}