描述

在一场策略游戏中，玩家需要将 n 名士兵排成一列，每个士兵有一个战斗力值。为了达到最佳阵型效果，玩家希望相邻两个士兵的战斗力之差的绝对值尽可能大。具体来说，定义一个排列的“阵型值”为所有相邻士兵战斗力差的绝对值之和。给定 n 个士兵的战斗力，请求出能获得最大阵型值的一种排列方式，并输出该最大阵型值。

注意：你需要重新排列这些士兵，使得阵型值最大。

输入输出格式

输入

第一行包含一个整数 n（2 ≤ n ≤ 10^5），表示士兵的数量。

第二行包含 n 个整数 a₁, a₂, ..., aₙ（1 ≤ aᵢ ≤ 10^9），表示每个士兵的战斗力。

输出

输出一个整数，表示最大可能的阵型值。

样例

4
1 3 1 4

6

限制

• 时间限制：1 秒
• 空间限制：256 MB
• 对于 100% 的数据，2 ≤ n ≤ 10^5，1 ≤ aᵢ ≤ 10^9