Trung vị của một tập hợp là số ~m~ sao cho ~m~ chia tập hợp đó thành 2 tập con có số lượng phần tử bằng nhau;

Để tìm trung vị của một tập hợp, người ta thường sắp xếp các phần tử của tập hợp đó theo thứ tự tăng dần. Nếu số lượng phần tử là lẻ thì giá trị ở vị trí ~(n+1)/2~ là trung vị, nếu số lượng phần tử là chẵn thì lấy trung bình cộng của hai số ở vị trí ~n/2~ và ~n/2+1~ làm trung vị. Với ~n~ là số lượng phần tử trong tập hợp, các vị trí của tập hợp được đánh số từ 1 đến ~n~.

Ví dụ với tập hợp ~{3,4,5}~ thì giá trị trung vị là ~4~; Với tập hợp ~{1,5,7,8,11,16}~ thì giá trị trung vị là ~(7+8)/2=7.5~

Yêu cầu: Bạn được cho lần lượt các số nguyên ~a_1,a_2,…,a_n~. Hãy cho biết giá trị trung vị của ~i~ ~(1≤i≤n)~ số đầu tiên.

Dữ liệu vào:

• Dòng đầu tiên ghi số nguyên ~n~ ~(1≤n≤10^5)~
• Dòng thứ ~i~ trong ~n~ dòng tiếp theo ghi số ~a_i~ ~(0≤a_i≤10^5)~

Kết quả:

• Ghi trên ~n~ dòng, trong đó dòng thứ ~i~ là giá trị trung vị của ~i~ số đầu tiên. Kết quả được ghi với độ chính xác một chữ số thập phân

Ví dụ:

Input

6
12
4
5
3
8
7 

Output

12.0
8.0
5.0
4.5
5.0
6.0