这个题除了最后一步都挺简单的。
首先观察到 \(a_i \le 2 \times 10^5\)，所以考虑对值域做事情。
依次从小到大考虑，你注意到一件很关键的事情：
- 当我插入 \(i + 1\) 这个数的时候，必须要先把序列中 \(i\) 的相邻对全部给消掉，否则 \(i\) 的相邻对就永远不可能消掉了。
这启示我们记录 \(i\) 的相邻对个数，因为前面的相邻对个数都为 \(0\) 了。
进一步思考，你会发现 \(i + 1\) 只能插入在 \(i\) 的相邻对之间，还有左右为 \(i\) 时可以插入在两边，然后插入时的贡献系数可以用插板法简单求出。
考虑设 \(f_{i, j, 0/1/2}\) 表示前 \(i\) 个数，\(i\) 的相邻对数量为 \(j\)，且左右边界有几个是 \(i\) 的方案数，仔细讨论一下，不难得出一个 \(O(n^2)\) 的做法。
你仔细想一想似乎没有办法优化了，但是此时你如果将 \(f_{i, j, 0/1/2}\) 不为 \(0\) 的位置打出来的话，你会发现，总状态数是 \(O(n)\) 级别的！第二维其实总大小是 \(O(n)\) 级别的，你可以用个 map，记一下暴力转移，然后原本 \(O(n^2)\) 就自然变成 \(O(n)\) 了。