题目描述

Monty Hall 是一个节目主持人，这一天，他决定推出一个新游戏。

总共有 $n$ 扇门围成一个圈，玩家现在站在第 1 扇门前，每个回合玩家会执行以下操作：选择一个数 $i$，花费 $C_i$ 的代价选择往右移动 $i$ 步，然后玩家打开他所在位置的门。特别地，保证 $C_i\geq C_{i+1}(1\leq i<n)$。

玩家想知道打开所有的门最少需要花费多少代价。

输入格式

第一行一个整数 $N(1\leq N\leq 10^5)$。

接下来 $N$ 个整数表示 $C_i(1\leq C_i\leq 10^5)$。

输出格式

一个整数，表示答案。

5
4 3 3 3 3

15