$\text{Description}$
有 $n$ 个所罗门，你需要执行以下两个操作：
- 花费 $x$，将你拥有的所罗门的编号都循环地加一。
- 花费 $a_i$，拥有第 $i$ 个所罗门
来获得所有所罗门，并最小化花费。
原题：$2\le n\le 2000$。
加强：$2\le n\le 10^6$。
$\text{Solution}$
首先有特别显然的结论。
每个所罗门一定都是从另一个所罗门变过来的。
设 $p(x)$ 表示第 $x$ 个所罗门是从第 $p(x)$ 个所罗门变过来的，$d(i)=p(i)-i+[p(i)<i]n$，换句话说，它是环上 $i$ 到 $p(i)$ 的顺时针距离。
那么对于一个 $p$，它的花费是：
构造很简单，将所有元素按照 $d$ 降序排列，然后依次执行对应的抓捕操作，接着执行对应次数的魔法操作即可。
这时就有个简单的做法，枚举 $\max_i d(i)$，那么 $x\max_i d(i)$ 就是定值，那我们知道对于 $p(i)$ 我们只需选择在范围内且 $a$ 最小的下标。
在原题的数据范围内，直接预处理所有区间的最小值就可以做到 $O(n^2)$。
记 $D=\max_i d(i),S(D)=\sum_{i}a_{p(i)}$。
转换一下思路，设 $c(i)$ 表示在某个 $D$ 下，$i$ 作为 $p(j)$ 出现的次数，也即 $#\{p(j)=i\}$，考虑怎么维护 $c(i)$ 的变化。
我们知道当 $D=0$ 时，所有 $c$ 都为 $1$。
我们发现，以 $D$ 为横坐标时，$c$ 在一般情况下是先增长，再不变，最后减少的样子（也有可能缺失某一部分）。
增长的话，意味着它向前扩张时没被后面的扩张。
不变的话有两种可能，一种是向前扩张时遇到一个更小的值，并且后面没有把自己扩掉，一种是向前扩张了，但是也被后面的扩张了。
减少的话，意味着没有向前扩张，但是被后面的值扩张了。
如果能预处理出 $c$，就能通过二次差分计算出 $S(D),D=0,1,\cdots,n-1$，现在问题转为对于每一个元素，计算它的 $c$ 函数，我们知道只需求出它的至多的两个拐点。
那我们直接使用单调栈预处理前后比它小的元素，就可以得出 $c$ 了。对于相等的元素，给它定个序就好了。
声明：由于细节过多，该做法暂未实现。
时间复杂度 $O(n)$。