喀山为即将举行的世界水上运动锦标赛新建了一个游泳池。

该游泳池有 $N$ 条泳道。部分泳道已经有游泳者在使用。鞑靼斯坦的科学家们将这些泳道分成了“幸运泳道”和“不幸运泳道”。不幸运泳道是指那些游泳人数最多的泳道。也就是说，不存在其他任何一条泳道的游泳人数比不幸运泳道还要多。在不幸运泳道中游泳的人会感到不开心。其余的泳道则被认为是幸运泳道，幸运泳道会让人们感到开心。

科学家们决定让更多的人感到开心。为此，他们与游泳池管理员达成了一项协议：如果需要，他们可以将最多一名游泳者从任意一条泳道移动到其相邻的泳道。第一条泳道上的游泳者只能移动到第二条泳道，最后一条泳道上的游泳者只能移动到倒数第二条泳道。

输入格式

第一行包含一个整数 $N$ — 游泳池中的泳道数量（$3 \le N \le 10^5$）。

第二行包含 $N$ 个用空格隔开的整数 $p_i$，描述各泳道之间的游泳者分布，其中 $p_i$ 是第 $i$ 条泳道上的游泳者人数（$0 \le p_i \le 10^5$）。

输出格式

输出一个整数 — 不开心的游泳者的最小可能数量。

样例

输入样例 1

3
1 3 5

输出样例 1

5

输入样例 2

4
1 0 1 0

输出样例 2

2