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 strengthof 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.

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.

Print n integers in one line. For each x from 1 to n, print the maximum strength among all groups of size x.

10
1 2 3 4 5 4 3 2 1 6

6 4 4 3 3 2 2 1 1 1

?

?

?

题目大意：

给出n个数，这n个数在区间长度为i（1~n）的时候可以分割成一些区间，这每个区间都会有一个最小值，在同样长度的这些区间的最小值中，输出最大值。

思路：利用单调栈，保持栈内单调递增。

单调栈：单调栈是以某一个值为最大（最小）值，向两个方向进行延伸，如果两边的数比他大（小），就进行延伸。并且利用栈可以使时间复杂度控制在O（n）。

#include
  
    #include
   
     #include
    
      #include
     
       #include
      
        #define LL __int64 using namespace std; struct node{ LL num,pre,next; }; //代表数字，前驱有几个，后继有几个。 LL max(LL a,LL b){ return a>b?a:b; } LL a[200005],ans[200005]; int main() { LL n,i,j; while(scanf(%I64d,&n)!=EOF) { stack
       
        Q; node tmp; memset(ans,0,sizeof(ans)); //ans数组记录i范围时的最大数字。 for(i=1;i<=n;i++) { scanf(%I64d,&a[i]); } tmp.num=a[1]; tmp.pre=tmp.next=1; Q.push(tmp); for(i=2;i<=n;i++) { node tmp1; tmp1.num=a[i]; tmp1.pre=tmp1.next=1; while(!Q.empty()&&Q.top().num>=tmp1.num) { tmp=Q.top(); Q.pop(); if(!Q.empty()) Q.top().next+=tmp.next; tmp1.pre+=tmp.pre; LL l=tmp.pre+tmp.next-1; //记录长度 ans[l]=max(ans[l],tmp.num); //比较长度为l 的ans大小。 } Q.push(tmp1); } while(!Q.empty()) { tmp=Q.top(); Q.pop(); if(!Q.empty()) Q.top().next+=tmp.next; LL l=tmp.pre+tmp.next-1; ans[l]=max(ans[l],tmp.num); } for(i=n-1;i>=1;i--) ans[i]=max(ans[i],ans[i+1]); //最后还要更新一下，可能中间有些长度没有被更新到。而且可以断定ans[i+1]>ans[i]一定成立。 for(i=1;i
        
       
      
     
    
   
  

?

?