Вам задано масив a_1, a_2, \ldots, a_{2n} довжиною . За одну операцію можна вибрати довільний індекс з 1 \leq i \leq 2n-1 і поміняти місцями a_i, a_{i+1}.
Для кожного від до n^2 знайдіть найбільшу можливу суму a_1 + a_2 + \ldots + a_n, яку можна отримати після виконання не більше операцій.
Перший рядок містить єдине ціле число .
Другий рядок містить цілих чисел a_1, a_2, \ldots, a_{2n} — елементи масиву.
1 \leq n \leq 100,
1 \leq a_i \leq 10^9.
Виведіть n^2 + 1 ціле число: найбільшу можливу суму a_1 + a_2 + \ldots + a_n, яку можна отримати, виконавши не більше 0, 1, 2, \ldots, n^2 операцій.
Приклад
Якщо не виконати жодної операції, сума a_1 + a_2 + a_3 = 1 + 2 + 3 = 6.
За одну операцію можна поміняти місцями a_3, a_4, отримавши a_1 + a_2 + a_3 = 1 + 2 + 4 = 7.