如果知道事与愿违，你是否会坚持。
考虑二分。
二分答案，check 函数要 \(O(n)\) 考虑。
排序不影响结果且更容易计算，故先进行排序。
记 \(cnt\) 为当前区间消耗的最小代价，\(sum\) 为本次记录的最小的 \(cnt\)。当前区间为 \(l \sim r\)，\(c_{i} = a_{i + 1} - a_{i}(1 \le i < n)\) 表示当前数和后数的差，\(mid\) 为区间长度。
根据题目理解，我们发现 \(cnt\) 即为 \(\sum_{i = l}^{r - 1} c_{i} \times i\)，即左数第一会被计算一次，第二被计算两次，以此类推。
考虑先计算出当前 \(mid\) 的第一个区间的 \(cnt\)，并令 \(sum \leftarrow cnt\)。
接着发现将区间右移一格后，\(cnt \leftarrow cnt - \sum_{i = l - 2}^{r - 2} c_{i} + c_{j} \times (mid - 1)\)，右移后，\(l - 2 \sim r - 2\) 的都会少计算一次，因为左端点右移，而 \(c_{j}\) 的加入会给后面的每个数带来 \(c_{j}\) 的代价，故加 \(c_{j} \times (mid - 1)\)。
至此考场上都想到了。
目前 check 为 \(O(n^{2})\)，考虑对 \(\sum_{i = l - 2}^{r - 2} c_{i}\) 进行前缀和优化，记 \(s_{i} = c_{i + 1} - c_{i}(1 \le i < n)\) 为 \(c\) 的前缀和，则 \(\sum_{i = l - 2}^{r - 2} c_{i} = s_{r - 2} - s_{l - 2}\)。
遗憾。