题目描述

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

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

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

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

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

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

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

输入格式

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

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

输出格式

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

样例

输入样例

5
4
7
8
6
4

输出样例

48

提示

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