什么叫我过了 ABD？什么叫 C 过题人数是 D 5 倍？
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
由于是排列，所以有一个很好的性质：nnn 会出现恰好一次。
所以对于每一个位置，它左边和右边恰好有一个最大值是 nnn，AiA_iAi 就是另一边的最大值。显然 iii 在 nnn 左侧时 AiA_iAi 单调不减，在右侧时 AiA_iAi 单调不增；Ai≤n−1A_i\le n-1Ai ≤n−1。
假设 nnn 的位置已经确定，我们统计答案。
假设 n=6,A=[1,4,4,4,5]n=6,A=[1,4,4,4,5]n=6,A=[1,4,4,4,5]，P6=nP_6=nP6 =n。
显然，AiA_iAi 更新一定是因为 PPP 的前缀 / 后缀最大值变大了，而这种情况只有 Pi=maxP[1,i]P_i=\max P_{[1,i]}Pi =maxP[1,i] 。所以所有 AiA_iAi 相同的块最左边 / 右边的答案就确定了。那么目前已知的 PPP 为 [1,4,?,?,5,6][1,4,?,?,5,6][1,4,?,?,5,6]。
块内其它答案呢？显然可以随便填，只要小于 AiA_iAi 即可。所以所有可能的 PPP 有 [1,4,2,3,5,6],[1,4,3,2,5,6][1,4,2,3,5,6],[1,4,3,2,5,6][1,4,2,3,5,6],[1,4,3,2,5,6]。
这是个简单数数问题，用求排列数即可。注意，如果 nnn 两端有 AiA_iAi 相同的块，那么就会出现两个 PiP_iPi 相同，不合法。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
现在我们确定 nnn 的位置。
观察样例，可以看出所有情况的 nnn 似乎都在 Ai=n−1A_i=n-1Ai =n−1 块两侧。
证明：
* 当 nnn 不在 Ai=n−1A_i=n-1Ai =n−1 的块中时，显然不符合“iii 在 nnn 左侧时 AiA_iAi 单调不减，在右侧时 AiA_iAi 单调不增”的性质。
* 当 nnn 在 Ai=n−1A_i=n-1Ai =n−1 的块中但不是两端时，注意到 nnn 左右两端都有一个 n−1n-1n−1，不符合刚刚的讨论。
而且这两种情况的确定的其它数的位置一定相同，所以答案直接 ×2\times 2×2 即可。
时间复杂度：O(∑n)O(\sum n)O(∑n)。
