题目描述

FJ建立了一个圆形的谷仓，包含𝑛(3≤𝑛≤1000)个排成环形的房间，按照顺时针编号为1…𝑛。每个房间与其两个相邻的房间相连，并且还有一扇通向谷仓外部的门。

FJ希望每个房间 𝑖 最终都能容纳恰好 𝑟𝑖 头奶牛（1≤𝑟𝑖≤100）。他计划打开一个单间的外门，让奶牛从那扇门进入。 然后每头奶牛顺时针穿过房间，直到到达合适的目的地。 FJ想要让他的奶牛集体行走最少的总距离。 如果他选择最佳的门来解锁，请确定他的奶牛需要步行的最小总距离。 单头奶牛行走的距离是她经过的内部门数量。

输入格式

输入分两行。

第一行包括𝑛。

接下来是𝑛个整数𝑟1...𝑟𝑛。

输出格式

请输出所有奶牛行走的最小总距离

样例 #1

样例输入 #1

5
4
7
8
6
4

样例输出 #1

48

提示

在这个例子中，最佳方案是选择2号房间作为入口。