AT_abc336_d [ABC336D] Pyramid

题目描述

对于正整数 $k$，金字塔数列（ピラミッド数列）是指长度为 $2k-1$ 的数列，其各项依次为 $1,2,\ldots,k-1,k,k-1,\ldots,2,1$。

给定一个长度为 $N$ 的数列 $A=(A_1,A_2,\ldots,A_N)$。
你可以对 $A$ 重复进行以下两种操作中的任意一种（可以操作 $0$ 次）：

• 选择数列中的一项，将其值减少 $1$。
• 删除数列的首项或末项。

请你求出，通过上述操作可以得到的金字塔数列的最大可能尺寸 $k$。

在本题的约束条件下，可以证明通过操作一定能得到至少一种金字塔数列。

输入格式

输入以如下格式从标准输入读入：

$N$ $A_1$ $A_2$ $\ldots$ $A_N$

输出格式

输出通过对数列 $A$ 重复进行题目描述中的操作后，能够得到的金字塔数列的最大尺寸。

输入输出样例 #1

输入 #1

5
2 2 3 1 1

输出 #1

2

输入输出样例 #2

输入 #2

5
1 2 3 4 5

输出 #2

3

输入输出样例 #3

输入 #3

1
1000000000

输出 #3

1

说明/提示

约束

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

样例解释 1

以 $A=(2,2,3,1,1)$ 为例，可以通过如下操作得到尺寸为 $2$ 的金字塔数列：

• 选择第 $3$ 项，将其减少 $1$，数列变为 $A=(2,2,2,1,1)$。
• 删除首项，数列变为 $A=(2,2,1,1)$。
• 删除末项，数列变为 $A=(2,2,1)$。
• 选择第 $1$ 项，将其减少 $1$，数列变为 $A=(1,2,1)$。

$(1,2,1)$ 就是尺寸为 $2$ 的金字塔数列。

另一方面，无论如何操作，都无法得到尺寸为 $3$ 或更大的金字塔数列，因此输出 $2$。

由 ChatGPT 4.1 翻译