题意：有序列 ，初始时为 ，执行下列操作
次：
给出最终的 ，求出可能的操作方案数。答案对 取模。
，时限 。
分析
若一个元素被操作了多次，那么显然只有最后一次操作有实际效果。
对于一个操作序列，我们对每个元素只保留最后一次操作，称作简化操作序列。
观察反射，对于一个长为 的简化操作序列，可以向其中插入若干无效操作，显然方案数只和
有关。
具体地，操作序列要求
个元素都存在，数值部分的方案数是
；此外还有方向部分，对于
个有效操作，方向确定，其余操作可以随意，方案数为 。
注意到我们钦定了
种元素最后出现的顺序，故方案数还需除以 。
接下来我们只需对简化操作序列计数。
正解
记被“移开头”的集合为 ，“移结尾”的集合为 ，则最后效果相当于
在左侧随意打乱，接上剩余的元素（按原序，即递增），然后 在右侧随意打乱。
我们找出排列中的一个递增区间 ，然后就能确定 。
此时简化操作序列长为 。能根据
确定前后两个方向操作的顺序，但它们可以随意归并，方案数为 。
枚举递增区间即可。
复杂度为 。
还有高手
所用的斯特林数可以卷积 求出。
记 为长为 的简化操作序列数。
记 的
为坏间隔，将整个序列划分为极长递增区间。极长递增区间的所有子区间恰组成递增区间集合。
记某个极长递增区间为 ，考虑其长为 的子区间的贡献：
注意到 每减小 ，在上标增大 的同时边界也扩大 ，这样的组合数部分和可以递推。
综上，本题的复杂度可以做到 。