У вас є чисел 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
У першому тестовому випадку є лише один спосіб розташувати числа по колу (не враховуючи обертання та симетрії) — (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. доларів.