原问题这个形式直接做不太好做，我们考虑换个角度思考这个问题。

考虑将这 $n$ 根木棍依次拼接在一起，此时会存在 $n+1$ 个端点，可以发现一次操作等价于把相邻的两个端点合并为这两个端点形成的区间中的任意一个整点位置，不过开头段和结尾段要特殊处理一下，因为你合并后会重新出现新的首尾端点。

考虑枚举最终每根木棍的长度，就能知道最终状态了，初始状态能转移到最终状态当且仅当初始状态的任意两个端点之间的区间至多只有最终状态中的一个端点。

暴力枚举 $\sum_{i=1}^{n} a_i$ 的每个因数 check 即可，时间复杂度 $O(n d(\sum a))$。

考虑再分析一下这个过程，对于一个长度为 $l$ 的段里面必定不会出现两个端点，因此最终的长度一定在 $[\frac{\max a}{2},2\max a]$ 之间，否则直接处理第一个 $> 2\max a$ 的因数即可，那么我们需要让复杂度最满需要找到一个因数个数尽量多的 $\sum a$ 并且需要找一个含有最多因数个数的区间 $[x,4x]$，此时 $\sum a = 963761198400$ 是最劣的，在区间 $[460161,1840644]$ 取到因数个数最大值 $882$ 个，由于此题有 6s 的时限，并且每次 check 都很难跑到严格 $O(n)$ 的复杂度，因此可以通过此题。

好像直接从左往右贪心做就是对的，倒闭啦。