作为当代建筑的爱好者，Farmer John 建造了一个圆形新谷仓，谷仓内部 n 个房间排成环形（3 \leq n \leq 1000），按顺时针顺序编号为 1\ldots n，每个房间都有通往与其相邻的左右房间的门，还有一扇门通往外面。

现在 FJ 有 n 头奶牛，他的目标是让每个房间恰好有一头奶牛。然而不幸的是，现在奶牛们随意呆在某个房间里，第 i 个房间里有 c_i 头奶牛。保证 \sum c_i =n。

第一行一个整数 n，接下来 n 行，第 i 行一个整数 c_i。

输出所有奶牛最小消耗能量和。