← 返回题目列表

AtCoder · awc0101_b

B. 多米诺骨牌的一次攻击

中文机器翻译题面 查看原题

分数: 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