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 *a*<sub class="lower-index">*i*</sub> 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*.
The first line of input contains integer *n* (1 ≤ *n* ≤ 2 × 10<sup class="upper-index">5</sup>), the number of bears.

The second line contains *n* integers separated by space, *a*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>, ..., *a*<sub class="lower-index">*n*</sub> (1 ≤ *a*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">9</sup>), heights of bears.
    N = int(input())
    heights = list(map(int, input().split()))
    left = [0]*N
    right = [0]*N
    min_from_left = [0]*N
    min_from_right = [0]*N
    max_strength = [0]*N
    left[0] = heights[0]
    for i in range(1,N):
        left[i] = min(left[i-1],heights[i])
    right[N-1] = heights[N-1]
    for i in range(N-2,-1,-1):
        right[i] = min(right[i+1],heights[i])
    for i in range(N):
        min_from_left[i] = min(left[i],right[i])
    for i in range(N):
        max_strength[i] = max(max_strength[i-1],min_from_left[i])
    print(" ".join(str(x) for x in max_strength))
#The above solution uses two arrays, left and right, to keep track of the minimum height from the left and right respectively, for each soldier. Then, it uses another array, min_from_left, to find the minimum of the two for each soldier. Finally, it iterates through the min_from_left array and keeps track of the maximum strength for each size x using max_strength array.

This approach avoids the nested loop and finds the solution in O(T*N) time complexity.




Regenerate respons