Сума суміжних чисел #12883

Сума суміжних чисел

1 секунда
256 мегабайтів
Складна

У вас є чисел a_1, a_2, \ldots, a_n. Ви хочете розташувати їх по колу так, щоб максимізувати суму добутків пар суміжних чисел.

Формально, ви хочете знайти перестановку b_1, b_2, \ldots, b_n a_1, a_2, \ldots, a_n таку, щоб b_1b_2 + b_2b_3 + \ldots + b_{n-1}b_n + b_nb_1 була максимальна.

Знайдіть це максимальне значення.

Вхідні дані

Перший рядок містить одне ціле число (1 \le t \le 10^4)  — кількість тестів. Нижче наведено опис тестових випадків.

Перший рядок кожного тесту містить одне ціле число (3 \le n \le 2\cdot 10^5)  — кількість чисел.

Другий рядок кожного тесту містить цілих чисел a_1, a_2, \ldots, a_n (-10^6 \le a_i \le 10^6).

Гарантується, що сума за всіма тестами не перевищує 2\cdot 10^5.

Вихідні дані

Для кожного тесту виведіть одне ціле число  — максимально можливе значення виразу b_1b_2 + b_2b_3 + \ldots + b_{n-1}b_n + b_nb_1 для всіх перестановок b_1, b_2, \ldots, b_n з a_1, a_2, \ldots, a_n.

Приклади

Приклад 1

Loading
Loading

Примітка

У першому тестовому випадку є лише один спосіб розташувати числа по колу (не враховуючи обертання та симетрії)  — (1, 2, 3). Сума добутків пар суміжних чисел дорівнює 1\cdot 2 + 2\cdot 3 + 3\cdot 1 = 11.

У другому тестовому випадку одним із оптимальних варіантів розташування є (1, 1, 1, 1, 0, 0). Для нього ця сума дорівнює 1 \cdot 1 + 1 \cdot 1 + 1 \cdot 1 + 1 \cdot 0 + 0 \cdot 0 + 0 \cdot 1 = 3.

У третьому тестовому випадку існує унікальний (з точністю до обертання та симетрії) спосіб розташування чисел у колі: (100000, 100000, 100000, 100000, -100000), відповідь 100000^2 = 10^ {10}. Зверніть увагу, що відповідь може не вписуватися в int32.

У четвертому тестовому випадку однією з оптимальних перестановок є (1, 2, 4, 5, 3), відповідь на яку1 \cdot 2 + 2 \cdot 4 + 4 \cdot 5 + 5 \cdot 3 + 3 \cdot 1 = 2 + 8 + 20 + 15 + 3 = 48. доларів.