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

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\).