分数: 300 分
问题陈述
有 N 高桥面前的柱子排成一排。的耐用性 i左起第 3 根柱子是 A_i.
高桥同时施加相同的力 X 所有支柱。每根受到冲击的柱子的耐久性都会降低 X.
之后,连锁反应从左向右传播。具体来说,当一根柱子倒塌时(其耐久性变为 0 或更少),紧邻其右侧的柱子的耐用性会额外降低 1。如果这导致右侧邻居也倒塌,则紧邻其右侧的柱子的耐用性会降低 1 也是如此。这条链条继续向右延伸,直到柱子不倒塌为止。请注意,如果最右边的柱子倒塌,不会发生进一步的连锁反应。
综上所述,每根柱子是否倒塌,从左到右按照以下规则判断:除了直接影响 X,支柱获得额外的 1 如果左侧的柱子倒塌,则会造成伤害。
找到最小值 X 需要倒塌所有支柱。 X 必须是正整数。
约束
- 1 \leq N \leq 5 \times 10^5
- 1 \leq A_i \leq 10^9
- 所有输入均为整数
输入
输入按以下格式给出。
N A_1 A_2 \ldots A_N
- 第一行给出了柱子的数量 N.
- 第二行给出 N 整数 A_1, A_2, \ldots, A_N 代表每根柱子的耐久性,以空格分隔。
输出
打印力的最小值 X 需要将所有支柱折叠成一条线。
示例输入 1
4 2 3 2 4
示例输出 1
3
示例输入 2
5 5 2 2 2 2
示例输出 2
5
示例输入 3
12 4 2 5 3 6 7 3 8 4 9 5 10
示例输出 3
9
示例输入 4
30 8 12 9 13 10 14 11 15 12 16 13 17 14 18 15 19 16 20 17 21 18 22 19 23 20 24 21 25 22 26
示例输出 4
25
示例输入 5
1 1000000000
示例输出 5
1000000000