Editorial

Нехай $a_i$ буде відсортована послідовність. Тобто, $a_i\le a_{i+1}$ для всіх $1\le i\le n-1$. Тоді відповіддю буде послідовність $a_n,a_1,a_{n-1},a_2,\dots$.

Доведення:

Ми будемо доводити це, використовуючи математичну індукцію.

База індукції буде 2 числа. Тоді відповідь це різниця між ними.

Нехай для всіх послідовностей $b_1,b_2,\dots ,b_{n-1}$ це буде правда. Тоді доведемо для послідовності $a_1,a_2,\dots ,a_n$. Ми знаємо, що $a_n-a_1$ буде найбільше серед всіх $a_i-a_j$ для всіх i та j. Тоді, видалимо $a_n$ з послідовності, та ми отримаємо послідовність $b_1,b_2,\dots ,b_{n-1}$, де $b_i=-a_{n-i}$, і тому послідовність залишається відсортованою. Через це $b_i-b_j=a_{n-j}-a_{n-i}$, і тому умова про різні різниці зберігається, і там відповідь буде $b_{n-1},b_1,b_{n-2},b_2,\dots$, що рівно $-a_1,-a_{n-1},-a_2,-a_{n-2},\dots$ тому також підходить послідовність $a_1,a_{n-1},a_2,a_{n-2},\dots$. Через те, що $a_n-a_1$ це найбільша можлива різниця у послідовності, ніде не зустрічається різниця, рівна цій. А тому, ми можемо додати на початок $a_n$, і тому рішення доведено.