题目描述

作为当代建筑的粉丝，农夫约翰建造了一个完美圆形的新谷仓。

在内部，谷仓由一圈$\red{n }$个房间组成，从谷仓周边的 $\red{1...}$$\red{n }$顺时针编号 $\red{(3≤}$$\red{n≤}$$\red{1,000)}$。

每个房间都有通往两个相邻房间的门，还有一扇通往谷仓外部的门。$\red{Farmer John }$希望 $\red{ri }$奶牛最终出现在每个房间$\red{i ( (1≤}$$\red{ri≤}$$\red{100)}$。

为了让奶牛有条不紊地进入牛舍，他计划打开一个单间的外门，让奶牛从那扇门进入。然后每头奶牛顺时针穿过房间，直到到达合适的目的地。

$\red{Farmer John }$想要打开外门，这将使他的奶牛集体行走最少的总距离。

如果他选择最好的门来解锁，请确定他的奶牛需要步行的最小总距离。

一头母牛走过的距离是她经过的室内门的数量。

输入格式

输入的第一行包含$\red{n}$

其余$\red{n }$行中的每一行都包含 $\red{r1…}$$\red{rn}$。

输出格式

请写出奶牛集体需要行驶的最小总距离。

样例

输入样例

5
4
7
8
6
4

输出样例

48

提示

在本例中，最好的解决方案是让奶牛通过需要$\red{7}$头奶牛的房间的门进入。