Есть \(n\) кубиков, пронумерованных от \(1\) до \(n\). Кубик \(i\) имеет вес \(a_i\).
У Пака Чанека есть \(3\) мешка с номерами от \(1\) до \(3\), которые изначально пусты. Каждый кубик Пак Чанек должен положить в один из мешков. После этого в каждом мешке должен оказаться хотя бы один кубик.
После того, как Пак Чанек разложит кубики, Бу Денгклек возьмет ровно по одному кубику из каждого мешка. Пусть \(w_j\) — вес кубика, который Бу Денгклек берет из мешка \(j\). Результатом всех действий назовем число \(|w_1 - w_2| + |w_2 - w_3|\), где \(|x|\) — модуль числа \(x\).
Известно, что Денгклек будет брать кубики таким образом, чтобы минимизировать результат. Чему равен максимально возможный результат, если Пак Чанек раскладывает кубики оптимально?
Выходные данные
Для каждого теста выведите строку, содержащую целое число, представляющее максимально возможный результат, если Пак Чанек оптимально разложит кубики.
Примечание
В первом наборе входных данные, один из вариантов получить итоговый результат, равный \(6\), выглядит следующим образом:
- Положить кубики \(1\), \(4\), и \(5\) в мешок \(1\).
- Положить кубик \(3\) в мешок \(2\).
- Положить кубик \(2\) в мешок \(3\).
Если Пак Чанек разложит кубики таким образом, то Денгклек может взять кубики следующим образом:
- Взять кубик \(5\) из мешка \(1\).
- Взять кубик \(3\) из мешка \(2\).
- Взять кубик \(2\) из мешка \(3\).
Результат равен \(|a_5 - a_3| + |a_3 - a_2| = |3 - 5| + |5 - 1| = 6\). Можно показать, что Бу Денгклек не может получить меньший результат при таком распределении кубиков.
Можно показать, что нет другого распределения кубиков, которое дает результат больший, чем \(6\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
5
3 1 5 2 3
4
17 8 19 45
8
265 265 265 265 265 265 265 265
|
6
63
0
|