ARC068F
额首先第一阶段，进入这个 deque 的时候，一定是一个单谷的状态。且 \(1\) 为最小值。
然后考虑后面我出队的时候，出到 \(1\) 的时候，剩下来 deque 里面一定是一段单调的序列。
也就是说，假如我钦定出队按元素大小，从大到小出，那么算出来的方案，在最后要乘上 \(2^{\max(0, n-k-1)}\)。不难发现目前这部分不会算重，也不会算漏。
这么钦定有什么好处呢？
这样一个结果序列合法，当且仅当她可以被分成两个单调递减的子序列。
然后由 Dilworth，等价于不存在一个长度为 \(3\) 的递增子序列。
这是第一个难点。
第二个难点是，我怎么设计状态，对 \(p_k=1\) 计数。
考虑逆排列 \(q\)。发现原排列的合法性和逆排列的合法性是等价的！
这样就要求 \(q_1=k\)。
设 \(f_{i,j}\) 表示，\(\{1,2,\dots, i\}\) 构成的排列中，\(q_1=j\) 的。
转移的话，考虑 \(q_2\) 的大小，分成 \(<j,=i-1,\text{otherwise}\) 三类。
不难稍微前缀和一下做到 \(O(n^2)\)。
更进一步地，可以把状态转移直接写成格路计数的形式。（归纳证明）
然后反射容斥做到线性。