Time Limit:1000MS Memory Limit:262144KB 64bit IO Format:%I64d & %I64u
Description
Mike is the president of country What-The-Fatherland. There are n bears living in this country besides Mike. All of them are standing in a line and they are numbered from 1 to n from left to right. i-th bear is exactly ai feet high.
A group of bears is a non-empty contiguous segment of the line. The size of a group is the number of bears in that group. The strength of a group is the minimum height of the bear in that group.
Mike is a curious to know for each x such that 1 ≤ x ≤ n the maximum strength among all groups of size x.
Input
The first line of input contains integer n (1 ≤ n ≤ 2 × 105), the number of bears.
The second line contains n integers separated by space, a1, a2, ..., an (1 ≤ ai ≤ 109), heights of bears.
Output
Print n integers in one line. For each x from 1 to n, print the maximum strength among all groups of size x.
Sample Input
10
1 2 3 4 5 4 3 2 1 6
/*
* Author: sweat123
* Created Time: 2016/7/12 10:39:09
* File Name: main.cpp
*/
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<string>
#include<vector>
#include<cstdio>
#include<time.h>
#include<cstring>
#include<iostream>
#include<algorithm>
#define INF 1<<30
#define MOD 1000000007
#define ll long long
#define lson l,m,rt<<1
#define key_value ch[ch[root][1]][0]
#define rson m+1,r,rt<<1|1
#define pi acos(-1.0)
using namespace std;
const int MAXN = ;
int a[MAXN],n,ans[MAXN];
struct node{
int len;
int val;
node(){}
node(int tlen,int tval):len(tlen),val(tval){}
};
stack<node>s;
int main(){
while(~scanf("%d",&n)){
for(int i = ; i <= n; i++){
scanf("%d",&a[i]);
}
while(!s.empty())s.pop();
memset(ans,,sizeof(ans));
for(int i = ; i <= n; i++){
int len = ;//表示当前弹出的这些元素能够贡献多少的长度
while(!s.empty()){
node tp = s.top();
if(tp.val < a[i])break;
s.pop();
int ret = tp.len + len;//这个元素能够贡献的长度 （也就是说这个元素已经统计过了多少长度，在这里也是可以连续的）
ans[ret] = max(ans[ret],tp.val);
len += tp.len;
}
s.push(node(len+,a[i]));
}
int len = ;
while(!s.empty()){
node tp = s.top();
s.pop();
int ret = len + tp.len;
ans[ret] = max(ans[ret],tp.val);
len += tp.len;
}
for(int i = n; i >= ; i--){
ans[i] = max(ans[i],ans[i+]);
}
for(int i = ; i <= n; i++){
printf("%d ",ans[i]);
}
printf("\n");
}
return ;
}