Обміни з максимальною сумою

Limits: 2 sec., 512 MiB

Вам задано масив $a_1, a_2, \ldots, a_{2n}$ довжиною $2n$. За одну операцію можна вибрати довільний індекс $i$ з $1 \leq i \leq 2n-1$ і поміняти місцями $a_i, a_{i+1}$.

Для кожного $k$ від $0$ до $n^2$ знайдіть найбільшу можливу суму $a_1 + a_2 + \ldots + a_n$, яку можна отримати після виконання не більше $k$ операцій.

Input

Перший рядок містить єдине ціле число $n$.

Другий рядок містить $2n$ цілих чисел $a_1, a_2, \ldots, a_{2n}$  — елементи масиву.

Output

Виведіть $n^2 + 1$ ціле число: найбільшу можливу суму $a_1 + a_2 + \ldots + a_n$, яку можна отримати, виконавши не більше $0, 1, 2, \ldots, n^2$ операцій.

Constraints

$1 \leq n \leq 100$,

$1 \leq a_i \leq 10^9$.

Samples

Input (stdin) сopy	Output (stdout) сopy
3 1 2 3 4 5 6	6 7 8 9 10 11 12 13 14 15

Notes

Якщо не виконати жодної операції, сума $a_1 + a_2 + a_3 = 1 + 2 + 3 = 6$.

За одну операцію можна поміняти місцями $a_3, a_4$, отримавши $a_1 + a_2 + a_3 = 1 + 2 + 4 = 7$.