该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

  Vasya是一个与怪物搏斗的巫师。现在有 $n$ 个怪物，第 $i$ 个怪物的血量为 $a_i$。

  Vasya是一个非常强大的巫师，会许多超强法术。在这场战斗中，他决定使用连锁闪电咒来打败所有怪物。让我们看看这个法术是如何使用的。

  首先，Vasya选择某个怪物下标 $i \space (1≤i≤n)$和咒语的初始威力 $x$。然后，咒语会准确地击中怪物们 $n$ 次，每个怪物命中一次。咒语的第一个目标总是怪物 $i$。

  除了第一个目标之外，连锁闪电会随机选择一个未被法术击中的怪物，该怪物与已被击中的怪物相邻。因此，每个怪物都会被击中一次。第一个被法术击中的怪物会受到 $x$ 伤害，第二个怪物受到 $(x-1)$ 伤害，第三个受到 $(x-2)$ 伤害，以此类推。

  Vasya想展示一下自己有多么强大，所以他想用一个连锁闪电咒杀死所有怪物。如果怪物受到的伤害不低于其血量，则视为死亡。另一方面，Vasya想表明他并不那么在乎，所以他想选择最小初始法术威力 $x$ 使其杀死所有怪物，不论怪物被击中的顺序如何。

  当然，Vasya是一名巫师，确定最佳法术设置所需的计算量远远超出了他的能力范围，因此你必须帮助他找到杀死所有怪物所需的最小法术威力。

  请注意，Vasya选择的是初始目标和法术威力，其他事情应视为随机，Vasya希望即使在最坏的情况下也能杀死所有怪物。

Format

Input

  输入的第一行包含一个整数 $n \space (1≤n≤3 \cdot 10^5)$ 表示怪物数量。

  输入的第二行包含 $n$ 个整数 $a_1, a_2, ..., a_n \space (1≤a_i≤10^9)$，其中 $a_i$ 是第 $i$ 个怪物的血量。

Output

  打印一个整数——如果Vasya以最佳方式选择了第一个目标后，杀死所有怪物所需的最小法术威力，法术命中的顺序可以是给定规则内的任何可能顺序。

Samples

6
2 1 5 6 4 3

8

5
4 4 4 4 4

8

2
1 1000000000

1000000000

提示

  由 $a_i \leq 10^9$ 可以推出结果的一个上界为 $2 \times 10^9$，为什么？