（说在前面：这篇题解写的非常长，并且没有 code，但是个人认为可以比较好的写明思考过程，如果你追求效率，请看其他题解）

点我！我是题目传送门

题意简述

海滩有 $n$ 个连续区段，第 $i$ 个区段上有 $a_i$ 枚琥珀。已知每一道海浪的宽度相同（均为 $k$），且恰好向连续的 $k$ 个区段各输送一枚琥珀（海浪可以任意多次使用），求可能的最大海浪宽度 $k$。

思路分析

将问题抽象：给定非负整数序列 $a_1,\dots,a_n$，是否存在非负整数序列 $b_1,\dots,b_{n-k+1}$（$b_j$ 表示以 $j$ 为起点的海浪数量），使得对于每个位置 $i$，

等价于用长度为 $k$ 的全 $1$ 区间（可重叠）去覆盖每个位置，覆盖次数恰好为 $a_i$，求最大的可行 $k$。

我们注意到

设 $m=n-k+1$，并定义前缀和 $B_i=\sum_{j=1}^i b_j$。通过分析覆盖关系可得：

• 对于 $i=1,\dots,m$，有 $a_i = B_i$（因为覆盖位置 $i$ 的区间起点只有 $1,\dots,i$）。
• 对于 $i=m+1,\dots,k-1$（如果存在），有 $a_i = B_m$。
• 对于 $i=k,\dots,n$，令 $j=i-k$，则 $a_i = B_m - B_j$。

由此可以导出使得 $k$ 可行的充要条件：

1. $a_1 \le a_2 \le \dots \le a_m$（废话，前缀当然是非递减的）。
2. 若 $m+1 \le n-m$，则区间 $[m+1,\;n-m]$ 内的所有 $a_i$ 均等于 $a_m$。
3. $a_{n-m+1} = a_m$（即 $a_k = a_m$）。
4. 对于所有 $j=1,\dots,m-1$，有 $a_j + a_{j+n-m+1} = a_m$。

其中 $m=n-k+1$。当 $k=1$ 时，任何序列都可行（每道浪只覆盖一个区段），故 $k=1$ 总是可行。

因此，我们可以从大到小枚举 $k$（即从小到大枚举 $m$），利用预处理快速检查上述条件。由于 $n\le 10^5$，直接枚举所有 $k$ 并 $O(1)$ 判断即可。

实现

预处理

• 前缀非递减：$inc[i]$ 表示 $a_1\le\cdots\le a_i$ 是否成立。
• 区间常数判断：$nxt[i]$ 表示从 $i$ 开始向右第一个不同于 $a_i$ 的位置（若不存在则为 $n+1$）。那么区间 $[l,r]$ 内所有值相等当且仅当 $nxt[l] > r$ 且 $a_l = a_r$（实际上 $nxt[l] > r$ 已保证全等）。
• 字符串哈希：用于快速比较后段 $[n-m+2,\;n]$ 与 $C - a[1..m-1]$（其中 $C=a_m$）。采用多项式哈希，模数 $10^9+7$，基数 $131$。预处理前缀哈希 $h[i]$、幂 $pow[i]$ 以及幂的前缀和 $spow[i]=\sum_{t=0}^{i-1} pow[t]$。

复杂度分析

• 预处理 $O(n)$，枚举 $k$ 最多 $n$ 次，每次检查 $O(1)$。
• 总时间复杂度 $O(n)$，空间复杂度 $O(n)$。