题解

思路

固定首次攻击位置 $i$。对 $j<i$，敌手可以先攻击右侧所有怪物，再逐步向左，因此怪物 $j$ 最晚在第 $n-j+1$ 次被攻击，需要 $x\ge a_j+n-j$。同理，对 $j>i$，它最晚在第 $j$ 次被攻击，需要 $x\ge a_j+j-1$。位置 $i$ 首次被攻击，只需 $x\ge a_i$。

于是固定 $i$ 的答案为三者最大值。前缀维护 $a_j+n-j$，后缀维护 $a_j+j-1$，即可线性枚举 $i$。

做法

令 left[i] 为 $1\le j\le i$ 时 $a_j+n-j$ 的最大值，right[i] 为 $i\le j\le n$ 时 $a_j+j-1$ 的最大值。

枚举首次位置 $i$，计算

越界项忽略。所有位置的最小值即为答案。

正确性证明

固定首次位置 $i$。任意 $j<i$ 必须在它右侧的左半段怪物之后被攻击，敌手还可在此之前攻击全部右半段，所以最晚攻击序号恰为 $n-j+1$；该顺序可以实现，故约束 $x\ge a_j+n-j$ 既必要又充分。对 $j>i$ 对称地得到必要且充分的约束 $x\ge a_j+j-1$，而 $i$ 的约束为 $x\ge a_i$。因此公式准确给出固定 $i$ 抵抗所有顺序所需的最小威力。枚举全部 $i$ 并取最小，得到全局最优答案。

复杂度分析

时间复杂度 $O(n)$，空间复杂度 $O(n)$。