← 返回题目列表

AtCoder · abc336_d

G. 金字塔

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

分数: 400 点

问题陈述

对于正整数 k, 金字塔序列 尺寸 k 是一个长度序列 (2k-1) 其中序列的项具有值 1,2,\ldots,k-1,k,k-1,\ldots,2,1 按此顺序。

给你一个序列 A=(A_1,A_2,\ldots,A_N) 长度 N.
找到通过重复选择并执行以下操作之一可以获得的金字塔序列的最大大小 A (可能为零次)。

  • 选择序列中的一项并将其值减少 1.
  • 删除第一项或最后一项。

可以证明,问题的约束保证通过重复运算可以得到至少一个金字塔序列。

约束

  • 1\leq N\leq 2\times 10^5
  • 1\leq A_i\leq 10^9
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N
A_1 A_2 \ldots A_N

输出

打印通过对序列重复执行问题陈述中描述的操作可以获得的金字塔序列的最大大小 A.


样本输入 1

5
2 2 3 1 1

示例输出 1

2

开始于 A=(2,2,3,1,1),您可以创建大小为金字塔序列 2 如下:

  • 选择第三项并将其减少 1。序列变为 A=(2,2,2,1,1).
  • 删除第一项。序列变为 A=(2,2,1,1).
  • 删除最后一项。序列变为 A=(2,2,1).
  • 选择第一项并将其减少 1。序列变为 A=(1,2,1).

(1,2,1) 是大小为的金字塔序列 2.
另一方面,无法执行创建大小为金字塔序列的操作 3 或更大,所以你应该打印 2.


示例输入 2

5
1 2 3 4 5

示例输出 2

3

示例输入 3

1
1000000000

示例输出 3

1