题目内容

塔子哥住的宿舍有一台电梯。大家有一个约定俗成的规矩:如果你要去的楼层的相邻楼层已经在之前被按下，则你不允许再按下按钮，等出电梯再自行上/下一层！

每个人都有一个想去的楼层$x_i$，这构成一个排队序列$S$.不同的入电梯顺序可能会导致不同的电梯按钮状态。例如:

$S = [1,2,3]$ , 那么电梯按钮状态为:$\{1,3\}$

$S = [2,3,1]$ , 那么电梯按钮状态为:$\{2\}$

从左至右为先后入电梯的顺序。

进一步讲，对于一种排队序列$S$ , 我们有一个冗余值$p(S)$ , 它描述的是最终大家需要爬楼的层数之和。例如:

$S = [1,2,3]$ , 那么 $p(S) = 1$ , 因为第2个人需要爬一层。

$S = [2,3,1]$ , 那么 $p(S) = 2$ , 因为第1,3个人都需要爬一层。

塔子哥是个圣母，他不是希望自己不需要爬楼，而是希望大家爬楼的总和尽量小(即最小化冗余值)。你能告诉他一种合理的排队序列，使得得到最小的冗余值是多少吗？

输入描述

第一行输入一个整数$n$ , 代表集合大小

第二行输入$n$个整数$s_i$, 代表每个人要去的楼层。

输出描述

输出一行代表集合的所有排列的效度之和。

数据范围说明

样例1

输入

3
1 2 3

输出

1

样例说明

让他们排成$[1,3,2]$ 或者$[3,1,2]$ 即可得到最小冗余值, 需要移动的人是要去第$2$楼的人,,所以冗余值是$2$

样例2

输入

6
1 2 2 2 2 3

输出

2

让他们排成$[2,2,2,2,1,3]$ 即可得到最小冗余值 , 需要移动的人是要去第$1,3$楼的人,所以冗余值是$2$