Cho một dãy \(N\) số nguyên \(a_1, a_2, ... , a_N\) đôi một khác nhau.

Ta định nghĩa phần tử trung vị của một dãy \(K\) số nguyên như sau: Sắp xếp các phần tử trong dãy \(K\) số nguyên trên theo thứ tự tăng dần. Sau khi sắp xếp xong:

• Nếu \(K\) lẻ, phần tử trung vị của dãy \(K\) số nguyên sẽ là phần tử thứ \((K + 1)/2\)
• Nếu \(K\) chẵn, phần tử trung vị của dãy \(K\) số nguyên sẽ là phần tử thứ \(K/2\).

Yêu cầu

Với mỗi \(i\) \((1 ≤ i ≤ N)\), hãy in ra phần tử trung vị của dãy \(a_1, a_2, ... , a_i.\)

Input:

• Dòng đầu tiên chứa 1 số nguyên dương \(N\) \((1 ≤ N ≤ 10^5).\)
• Dòng tiếp theo chứa \(N\) số nguyên \(a_1, a_2, ... , a_N\) \((|a_i| ≤ 10^9\)).

Output

In ra trên \(N\) dòng, dòng thứ \(i\) là giá trị phần tử trung vị của dãy \(a_1 → a_i\).

Example

Gợi ý: Sử dụng Set, thêm từng phần tử vào trong Set. Song song với đó, ta duy trì một con trỏ ở trên Set sao cho con trỏ luôn nằm ở phần tử trung vị của dãy.