记录编号	315365	评测结果	AAAAAAAAAA
题目名称	2485.[HZOI 2016]从零开始的序列	最终得分	100
用户昵称	Sky_miner	是否通过	通过
代码语言	C++	运行时间	0.075 s
提交时间	2016-10-05 07:51:11	内存使用	4.10 MiB

#include <algorithm>
#include <cstdio>
using namespace std;
inline void read(int &x){
	x=0;char ch;bool flag = false;
	while(ch=getchar(),ch<'!');if(ch == '!') ch=getchar(),flag = true;
	while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;
}
inline int cat_min(const int &a,const int &b){return a<b ? a:b;}
inline int cat_max(const int &a,const int &b){return a>b ? a:b;}
const int maxn = 200010;
int n,a[maxn],fa[maxn],h[maxn];
inline int find(int x){return fa[x] == x ? x : fa[x] = find(find(fa[x]));}
bool cmp(const int &i,const int &j){
	return a[i] == a[j] ? i < j : a[i] < a[j];
}
int siz[maxn],f[maxn],t;
inline void update(int x){
	fa[x] = x;siz[x] = 1;
	if(t = find(x-1)) fa[t] = x,siz[x] += siz[t];
	if(t = find(x+1)) fa[t] = x,siz[x] += siz[t];
	f[siz[x]] = cat_max(f[siz[x]],a[x]);
}
int main(){
	freopen("sky_seq.in","r",stdin);
	freopen("sky_seq.out","w",stdout);
	int n;read(n);
	for(int i=1;i<=n;++i) read(a[i]),h[i] = i;
	sort(h+1,h+n+1,cmp);
	for(int i=n;i>=1;--i) update(h[i]);
	for(int i=n;i>=1;--i) f[i] = cat_max(f[i],f[i+1]);
	for(int i=1;i<=n;++i) printf("%d ",f[i]);
	getchar();getchar();
	return 0;
}