Một trạm khí tượng ghi nhận nhiệt độ mỗi ngày. Các nhà khoa học muốn theo dõi nhiệt độ trung vị (median) của tất cả các ngày đã qua. Cụ thể, sau mỗi ngày có số liệu mới, họ muốn biết nhiệt độ trung vị của dãy nhiệt độ tính đến thời điểm hiện tại.

Trung vị được định nghĩa: với dãy đã sắp xếp, nếu số phần tử lẻ thì trung vị là phần tử ở vị trí (N+1)/2, nếu chẵn thì là phần tử ở vị trí N/2.

Đầu vào

• Dòng đầu chứa số nguyên N (1 ≤ N ≤ 10^5) — số ngày.
• Dòng hai chứa N số nguyên A_i (1 ≤ A_i ≤ 10^9) — nhiệt độ các ngày.

Đầu ra

In ra N dòng, dòng thứ i là trung vị của dãy A_1..A_i.

Ví dụ

Input:
8
1 5 3 2 4 6 8 7

Output:
1
1
3
2
3
3
4
4