Cho một mảng gồm \(n\) số nguyên, xét các cách ghép thành \(k\) cặp. Mỗi số có thể xuất hiện trong nhiều nhất một cặp, và chi phí của một cặp \((a,b)\) là \(|a-b|\). Chi phí của một cách ghép cặp là tổng chi phí của tất cả các cặp.

Hãy tính chi phí nhỏ nhất của các cách ghép cặp với \(k=1,2,\dots,\lfloor n/2 \rfloor\).

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên: kích thước của mảng.

Dòng tiếp theo chứa \(n\) số nguyên \(x_1,x_2,\dots,x_n\): các phần tử của mảng.

Dữ liệu ra

In ra \(\lfloor n/2 \rfloor\) số nguyên: chi phí nhỏ nhất của các cách ghép cặp.

Constraints

• \(2 \le n \le 2 \cdot 10^5\)

• \(1 \le x_i \le 10^9\)

Example

8
3 1 2 7 9 3 4 7

0 0 1 6

Explanation

Các cách ghép cặp có chi phí nhỏ nhất có thể là \([(3,3)]\), \([(3,3),(7,7)]\), \([(1,2),(3,3),(7,7)]\) và \([(1,2),(3,3),(4,7),(7,9)]\).