完整版实在是太长了，所有分析就列在博客里了，这里简述 AC 做法。

不难观察到最后一段和越小答案越小。

令 $dp(i)$ 为 $i$ 结尾时的最小取值，$pos_i$ 为 $i$ 取得最小值时所处段前一段的最后一个元素。

有 $dp(i) = dp(pos_i) + (s_i - s_{pos_i})^2$

求出 $a$ 的前缀和数组 $s$。

用一个单调队列维护 $2\times s_j - s_{pos_j}$，当队首和队首后一个元素都满足 $2 \times s_j - s_{pos_j} \le s_i$ 时，循环删除队首。

由于数据很大，只存储 $pos$ 数组，答案最后统一计算即可。