首先考虑边缘的数值域只有 2 怎么做。考虑网络流，通过让 i 与 S 连通来代表 i 选 1，与 T 连通代表 i 选 2。相邻的两个点连一条权值为 1 的双向边。不考虑边界上已经确定的点，用与 S/T 直接连边替代与它们连边。这样就能做到 O(n^2) 了。
显然存在一个最优解，你需要填的数就是边缘出现过的数。
断言：对于每一个 v，令 f(v) 为把边缘点设置成 a_i \ge v 所求得的答案，则整个问题的答案为 \sum_v f(v)。
（具体不会证明）
有了这个断言，于是就可以枚举扫描线的 v 的范围（显然有 n 个）。最开始求一遍网络流是 O((n^2)^{1.5})，即 O(n^3)。观察到所有点的流量都为 1，并且边变化的条数只有 O(1)，于是考虑退流。
具体地，当需要删掉一条边的时候，假定该边有流量，且设流量方向为 (u,v)，则先将全局最大流减去该边流量，则跑一遍以 u 为源点，S 为汇点的最大流，然后再跑一遍以 T 为源点，v 为汇点的最大流。最后再跑一次最大流，把求得的数值加到全局最大流上。一轮增广复杂度为 O(n^2)，会变化 n 次，所以时间复杂度仍为 O(n^3)。