B. Mike and Feet

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

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.

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.

Example

10
1 2 3 4 5 4 3 2 1 6

Output

6 4 4 3 3 2 2 1 1 1


Lets us understand few things
(1) Lets consider that an element a[i] is smallest upto l on its left side and upto 
r on its right side In other words , a[l-1]>a[i] && a[r+1]>a[i]. Hence the element a[i] spans all the subsegments that starts from a[l] and covers atleast a[i] the element and and subsegment that covers a[i]th element and upto a[r].Lets call this as the span 
of the subsegment. Let the length of  span[a[i]]= r-l+1. Now lets this length be l. Hence this length is a canditate answer for any lenght t where t<=l .
Now we simply calculate the maximum values of using the backward array and keeping in mind the fact that for any length l it can be a canditate answer for all length  t such that 
1<=t<=l . Now how do we do this 
(1) o(n^2) logic :- for fixing the best answer for length l we take maximum values among 
all the spans form length   t  where l<=t<=n. In other words ans[kth subsegment]=max(ans[k+1], ans[k+2],.....ans[n]);  Doing this for all element will yield  us 
o(n^2).   
(2) we reduce this to O(n) by setting the value from backward.

 ***************************THE CODE FOLLOWS****************************
#include<bits/stdc++.h>
using namespace std;
int a[200010];
int rt[200010];
int lt[200010];
int n;
void calcspan()
{
    stack<int> s;
    
    
    for(int i=1;i<=n;i++)
    {
            while(!s.empty() && a[s.top()]>a[i])
            {
                      rt[s.top()]=i-1;
       s.pop();  
      }
      s.push(i);
    }
    while(!s.empty())
    {
          rt[s.top()]=n;
          s.pop();
    }
    for(int i=n;i>=1;i--)
    {
        while(!s.empty() && a[s.top()]>a[i])
        {
            lt[s.top()]=i+1;
            s.pop();
   }
   s.push(i);
   }
   while(!s.empty())
   {
       lt[s.top()]=1;
       s.pop();
   }
}
int span[200010];
int maxi[200010];
int b[2000010];
int main()
{
   //int n;
   cin>>n;
   for(int i=1;i<=n;i++)
   {
    cin>>a[i];
   }
   calcspan();
   for(int i=1;i<=n;i++)
   {
      span[i]=(rt[i]-lt[i]+1);
   }
 /*  for(int i=1;i<=n;i++)
   {
     // cout<<span[i]<<" ";
     cout<<rt[i]<<" ";
   }
   cout<<endl;
   for(int i=1;i<=n;i++)
   {
          cout<<lt[i]<<" ";
   }
   cout<<endl;
   for(int i=1;i<=n;i++)
   cout<<span[i]<<" ";
   cout<<endl;
   cout<<endl;*/
  
   for(int i=1;i<=n;i++)
   {
       maxi[span[i]]=max(maxi[span[i]],a[i]);
   }
   /* for(int i=1;i<=n;i++)
   cout<<maxi[i]<<" ";
   cout<<endl;*/
   b[n+1]=0;
   for(int i=n;i>=1;i--)
   {
        b[i]=max(maxi[i],b[i+1]);     
   }
   for(int i=1;i<=n;i++)
   cout<<b[i]<<" ";
   cout<<endl;
}