Cho một dãy gồm \(n\) số nguyên: \(a_1, a_2, \ldots, a_n\).

Với mỗi chỉ số \(i\) từ \(1\) đến \(n\), hãy xác định trung vị của dãy con gồm các phần tử từ \(a_1\) đến \(a_i\) (tức là dãy \(a_1, a_2, \ldots, a_i\)).

Trung vị của một dãy gồm \(k\) phần tử là phần tử ở vị trí thứ \(\left\lfloor \frac{k+1}{2} \right\rfloor\) nếu sắp xếp dãy đó theo thứ tự không giảm.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên \(n\) \((1 \leq n \leq 10^6)\).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) \((|a_i| \leq 10^9)\).

Dữ liệu ra

• In ra \(n\) số nguyên — trung vị của các dãy con [\(a_1\)], [\(a_1, a_2\)], ..., [\(a_1, a_2, \ldots, a_n\)], mỗi trung vị trên một dòng hoặc cách nhau bởi dấu cách.

Input 1

5
1 2 3 4 5

Output 1

1 1 2 2 3