一个 $\text{poly}(n)$ 做法：

考虑确定所有最大值的位置，然后递归到若干个子问题中.

枚举第一个最大值的位置，然后就可以依次确定所有最大值的位置.

这个做法关键问题在于，最大值的位置集合不是唯一的.

考虑换个思路：确定所有非严格前缀最大值的位置. 设为 $p_1=1,p_2,\cdots,p_k$，然后划分为 $k+1$ 个子问题.

设 $c$ 满足，$2\sim c$ 可以和 $1$ 联络，$c+1$ 不可以和 $1$ 联络，那么必然有 $a_{2\sim c-1}\leq a_1,a_c>a_1$，且 $h_1\leq h_c$.

不难发现，把 $h_1$ 调整为 $h_c$ 后不会改变 $a$，于是我们就找到了 $p_2$.

接下来，设 $y$ 为某个非严格前缀最大值，$x$ 满足 $h_x\geq h_y,x < y$ 且最大（没有则 $x=1$），$s$ 为 $h_{x\sim n}$ 中的严格前缀最大值数量减 $1$. 我们希望找到下一个非严格前缀最大值，并维护 $x,s$.

考虑 $y$ 可以和哪些点联络，可以发现只能是 $[x,y-1]$，右边的 $s$ 个严格前缀最大值，以及 $[y+1,z]$. $z$ 可以计算得出.

若 $z=n$，则不存在下一个非严格前缀最大值，否则有三种情况：

1. $y=z$，那么意味着 $h_{y+1}>h_y$.
2. $h_y=h_z$.
3. $h_y > h_z,h_y < h_{z+1}$.

我们希望区分后两种情况.

若是第二种情况，则必有 $a_z\geq z-y+s$.

若是第三种情况，且 $a_z\geq z-y+s$，则可以将 $h_z$ 增加为 $h_y$，这样不改变 $a$，调整为情况二.

因此若 $a_z\geq z-y+s$ 则为情况二，否则为情况三.

复杂度 $O(n)$.