有 $n$ 个人正在玩一个游戏。这些人编号为 $1$ 到 $n$。每一轮游戏可以由 $1$ 到 $n-1$ 个人参与。
此外，你有一个包含 $n$ 个元素的数组 $a$。
设 $b_i$ 表示第 $i$ 个人参与而第 $(i+1) \pmod n$ 个人不参与的轮数。 设 $c_i$ 表示第 $(i+1) \pmod n$ 个人参与而第 $i$ 个人不参与的轮数。
你必须保证对于每一个 $i$，满足 $b_i + c_i \le a_i$，否则第 $i$ 个人会不高兴。
作为主持人，你希望决定如何进行这些轮次，以最大化总轮数。为了简单起见，你只需要输出这个最大化的数值。
输入格式
第一行包含一个整数 $n$ ($2 \le n \le 2 \times 10^5$)。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^9$)。
输出格式
仅一行，包含一个整数，表示可以进行的最大轮数。
样例
输入 1
2 7 5
输出 1
5