显然 $>2$ 的数后面的一定比它小，因此序列一定是两段递减的序列，分别以 $1$ 和 $2$ 结尾。从大往小加数，设 $f(i,j)$ 为加完 $n,n-1,\ldots,i$ 之后，两个序列分别以 $i$ 和 $j$ 结尾的方案数。首先 $i$ 一定可以直接接在 $i+1$ 的后面，所以 $f(i,*)$ 相比 $f(i+1,*)$ 的变化只有 $f(i,i+1)$，可以直接枚举另一边的数计算。时间复杂度 $O(n\log n)$。