比武大会

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

一年一度的天下第一比武大会又开始了。按照惯例,参赛者们围成了一个圆圈,每个人可以跟他相邻的人决斗,胜利者留在原地,而失败者立刻淘汰出局。

大会的组织者已经算出每位选手的能力值,能力值大的一定可以战胜能力值小的(能力值相同时,不会有平局,必有一方被淘汰)。同时为了让比赛更加激烈,他们倾向于让能力值接近的两名选手打斗。所以他们想安排一个比武的顺序,在不改变参赛者现在位置的条件下,使得所有比赛中两名选手能力值差别的总和最小。

Input

第1行1个整数n,表示参赛的人数(2<=n<=2000)。

第2行有n个数,依次表示圆上第1,2,...,n个人的能力值(能力值为不超过10000的非负数)。显然,第n个人和第1个人相邻。

Output

一个整数,为n-1场比赛双方能力值差的绝对值之和的最小值。

Sample Input

3
2 3 1

Sample Output

2

Hint

Source