Unimodal Permutation
给定一个{1, 2, ... N}的排列P，每次可以将其中一个数移动到最左边，问最少需要几次移动可以使P变成一个单峰的排列。
例如{4, 3, 1, 5, 2}可以通过依次移动数字3和1，变成{1, 3, 4, 5, 2}。
首先我们可以发现
(1)没有被移动的数会按原顺序集中在排列右端。
还是以{4, 3, 1, 5, 2}为例，如果我们决定移动1和3(先移动1还是3顺序暂未定)，那么最后的排列一定是{X, Y, 4, 5, 2}，4、5和2一定按顺序集中在最右端。同时
(2)我们可以随心所欲安排被移动的数字的顺序。
也就是说无论X=1, Y=3还是X=3, Y=1我们都可以做到。只要先移动最终位置靠右的数即可。
(3)每个数最多只需要被移动一次。
之后我们进一步分析这个问题。既然我们要移动的次数最少，也就是上文(1)中所述的“没有被移动的、按原顺序集中在排列右端”的数越多越好。
我们分情况讨论这部分数列与最终整个单峰排列的关系。
A. 最终的单峰排列退化为单调递增的排列，这时没有被移动的部分一定是{1, 2, 3, ... N}的某个一个后缀。
举个例子，对于{3, 4, 5, 2, 1, 6, 7, 8}，最少移动2次变成{1, 2, 3, 4, 5, 6, 7, 8}。这时没有被移动的部分是{3, 4, 5, 6, 7, 8}。
对于这种情况，我们要“没有被移动的数”尽量多，是有贪心做法的。我们只需要依次查找N, N-1, N-2 ... 在原排列中的位置，如果位置不断左移，那么我们就能把这些数都保留下来；直到遇见一个某个数X的位置在X+1右边，这时我们只能停下来，保留X+1 ... N不动，1 .. X都需要移动。
B. 最终的单峰排列退化成单调递减的排列，这时没有被移动的部分一定是{N, N-1, N-2, ... 1}的某个一个后缀。
举个例子，对于{6, 5, 4, 7, 8, 3, 2, 1}，最少移动2次变成{8, 7, 6, 5, 4, 3, 2, 1}。这时没有被移动的部分是{6, 5, 4, 3, 2, 1}。
这种情况与A类似，也是有贪心做法的。我们只需要依次查找1, 2, 3 ... 在原排列中的位置，如果位置不断左移，那么我们就能把这些数都保留下来；直到遇见一个某个数X的位置在X-1右边，这时我们只能停下来，保留1 ... X-1不动，X ... N都需要移动。
C. 最终的单峰排列是真正的单峰排列。为了描述方便，我们设定这个排列是{Lp, Lp-1, ... L1, N, R1, R2, ... Rq}。我们称{Lp, Lp-1, ... L1, N}为左支，显然左支是单调递增的；{N, R1, R2, ... Rq}是右支，显然右支是单调递减的。p + q = N-1。
现在我们再考虑没有被移动的部分在最终排列中的位置。分两种情况：
C1. 没有被移动的部分完全处于右支{N, R1, R2, ... Rq}中。
举个例子，对于{8, 6, 5, 4, 7, 3, 2, 1}，最少移动一次变成{7, 8, 6, 5, 4, 3, 2, 1}。没有移动的部分是{8, 6, 5, 4, 3, 2, 1}完全处于右支。
这种情况下，没有被移动的部分一定是原排列中的一个单调递减子序列。所以这部分最长就是原序列的最长单调递减子序列。幸运的是， 只移动最长单调递减子序列之外的数是一定可以形成单峰排列的。 因为根据(2)我们只需要把单调递减子序列之外的数按从小到大顺序排在左边即可。
C2. 没有被移动的部分左边跨过了N，是{Lk, Lk-1, ... L1, N, R1, R2, ... Rq}。前面3种情况都比较简单，这是最后一种情况，也是最难的情况。
举个例子，对于{4, 6, 1, 8, 7, 2, 5, 3}，最少移动2次变成{1, 2, 4, 6, 8, 7, 5, 3}。这时没有被移动的部分是{4, 6, 8, 7, 5, 3}。
在这种情况下，我们知道最大数N一定不被移动，同时我们要安排左支不被移动的数和右支不被移动的数，使得最终左右两支不被移动的数的总数尽量大，同时被移动的数还必须满足从小到大放在左端时不会破坏单峰的性质。
在这种情况下，有几个重要的结论：
(4)如果k确定，那么Lk, Lk-1, ... L1也是确定的。换句话说，如果我们知道最终左支中有几个数是没有被移动的，那么具体是哪几个数也是确定的。
举个例子，对于{4, 6, 1, 8, 7, 2, 5, 3}，我们知道8一定没被移动，假设我们确定左支中还有1个数是没被移动的，那么这个数是几？
我们稍微分析一下就能确定这个没被移动的数只能是6。否则我们假设是4没被移动，那么6就必然是被移动的，6就必然在4的左边，这时{..., 6, ... 4, ... 8, ... }一定不能形成单峰排列。
换句话说，L1一定是N左边的数中最大的数。
那么L2呢？ 同理我们可知如果L2存在，那么L2一定是N左边的数中第二大的数。例如对于{4, 6, 1, 8, 7, 2, 5, 3}，L2是4。
所以Li一定是N左边的数中第i大的数。不过值得注意的是，当i逐渐变大时，Li不一定存在。例如对于{4, 6, 1, 8, 7, 2, 5, 3}，L3是不存在的，也就是说左支除了8最多保留{4, 6}两个数。原因是8左边第三大的数1的位置在第二大的数4的右边。
(5)如果左支不被移动的数Lk, Lk-1, ... L1确定，那么右支不被移动的最优方案(如果存在合法的方案)也是确定并且容易求出的。
如果左支不被移动的数Lk, Lk-1, ... L1确定，那么首先N右边所有大于Lk的数都必须不被移动，否则它们会被移动到Lk左边，一定不能形成单峰排列。
既然N右边所有大于Lk的数都必须不被移动，那么它们在原排列中必须是单调递减的。
举个例子，对于{3, 7, 10, 9, 8, 5, 4, 6, 2, 1}，假设左支不被移动的是{3, 7, 10}，那么10右边所有大于3的数都不能被移动，但是{9, 8, 5, 4, 6}又不是单调递减的，所以必然不能形成单峰排列。也就是说假设左支{3, 7, 10}不被移动是不成立的。
如果假设左支不被移动的是{7, 10}，那么10右边所有大于7的数都不能被移动，这时{9, 8}是单调递减的，所以至少存在一种方案只保留{7, 10, 9, 8}，其他数都移动到左边。
当然这种方法并不是最优的，我们要寻找保留{7, 10, 9, 8}的情况下，右支最多还能有多少数不被移动。这个最大值显然是从8开始向右的最长递减子序列{8, 5, 4, 2, 1}。也就是保留{7, 10, 9, 8, 5, 4, 2, 1}不被移动。
综上所述，如果我们确定左支不被移动的数的个数k，那么具体不被移动的数Lk, Lk-1, ... L1就确定下来了（或者左支方案不存在）；同时右支最优方案也可以通过求最长下降子序列确定下来（或者右支方案不存在）。
通过一些预处理，整个算法的复杂度可以优化到O(NlogN)，其中排序和求最长下降子序列是瓶颈。不过考虑到O(NlogN)求最长下降子序列并不是本题的关键考察点，所以数据中N<=1000，O(N^2)的算法也可以拿满分。
