Cột trụ

Có $n$ cột trụ được dựng thẳng hàng và được đánh số từ $1$ đến $n$ theo thứ tự từ trái sang phải. Cột trụ thứ $i$ có độ cao là $a_i$.

Một nhóm cột là một đoạn con liên tiếp không rỗng gồm các cột kề nhau trên hàng. Kích thước của một nhóm cột là số lượng cột trụ trong nhóm đó. Độ chịu lực của một nhóm cột là độ cao nhỏ nhất trong số các cột trụ thuộc nhóm đó.

Với mỗi giá trị $x$ thỏa mãn $1 ≤ x ≤ n$, hãy tìm độ chịu lực lớn nhất trong tất cả các nhóm cột có kích thước bằng $x$.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên $n$ ($1 ≤ n ≤ 2 × 10^5$), biểu thị số lượng cột trụ.

Dòng thứ hai chứa $n$ số nguyên phân tách bởi dấu cách, $a_1, a_2, ..., a_n$ ($1 ≤ a_i ≤ 10^9$), trong đó $a_i$ biểu thị độ cao của cột trụ thứ $i$.

Kết quả

In ra $n$ số nguyên trên một dòng, phân tách bởi dấu cách. Trong đó, số thứ $x$ ($1 ≤ x ≤ n$) biểu thị độ chịu lực lớn nhất trong tất cả các nhóm cột có kích thước bằng $x$.

Chấm điểm

Subtask 1 (30 points). $n ≤ 4000$

Subtask 2 (70 points). $1 ≤ n ≤ 2 × 10^5$

Ví dụ

Input

10
1 2 3 4 5 4 3 2 1 6

Output

6 4 4 3 3 2 2 1 1 1

Ghi chú

Trong ví dụ trên, với dãy độ cao $a = [1, 2, 3, 4, 5, 4, 3, 2, 1, 6]$:

Với $x = 1$, nhóm $[6]$ có độ chịu lực bằng $6$, đây là giá trị lớn nhất trong tất cả các nhóm kích thước $1$.

Với $x = 2$, nhóm $[4, 5]$ có độ chịu lực bằng $\min(4, 5) = 4$.

Với $x = 3$, nhóm $[4, 5, 4]$ có độ chịu lực bằng $\min(4, 5, 4) = 4$.

Với $x = 4$ và $x = 5$, các nhóm $[3, 4, 5, 4]$ và $[3, 4, 5, 4, 3]$ đều có độ chịu lực bằng $3$.

Với $x = 6$ và $x = 7$, các nhóm $[2, 3, 4, 5, 4, 3]$ và $[2, 3, 4, 5, 4, 3, 2]$ đều có độ chịu lực bằng $2$.

Với $x ≥ 8$, mọi nhóm đều chứa ít nhất một cột trụ có độ cao bằng $1$, do đó độ chịu lực lớn nhất là $1$.