在幼儿园里，老师让小朋友站成一条线，每连续几个人要分成一组，这个分组有个原则，希望组里的小朋友差异度最大。这个差异度是这样定义的，每个小朋友有一个个性值，一个小组的差异度为这个小组中最大个性值减最小个性值。问怎样分组，可以使得所有分组的差异度之和最大，输出这个最大差异度之和。

输入n，表示有n个小朋友

然后一行输入n个整数ai，表示每个小朋友的个性值

输出最大差异度之和

【样例说明】

可以【1 2 3】【1 2】分，差异度之和为2+1=3

也可以【1 2】【3 1 2】分，差异度之和为1+2=3

其他样例：

输入：

3

3 3 3

输出：

0

【数据规模和约定】

1<=n<=10^6

-10^9<=ai<=10^9