非常骚的一道题
首先看数据范围就很像dp（而且在dp专题里），尝试直接dp，发现不太行
手玩一波样例，发现答案是 2的若干次方乘一个系数。我们发现 “若干”=n-k-1，这是巧合吗！？
思索一番，会发现当我们取完k个数后 剩下的n-k个数 取法就为 2^(n-k-1) ，为什么呢？
可以把每次操作看成 “前取“”or “后取”，一共n-k次操作，最后一个数前取后取都一样，也就是2^(n-k-1)
这时候就可以把原问题化为 取前k个的方案数 * 2^(n-k-1)，这下可以dp了吗？
先考虑一下入队列后 队列的样子 一定是
q1 > q2 > q3 >……> qi-1> qi =1 < qi+1……< qn
明显在取前k-1个数时，我们只能从两边往中间取，并且不会取到1。
所以可以看成在两个栈（上式中的q1~qi-1,qi+1~n）中交错取数，而且肯定有一个栈的大小<k（才能在第k个取到1）。
定义二栈为大小<k 的站，另外一个为1栈。
可以把过程想象成 从二栈中取数，插在一栈中间。
example:
一栈：qn……qi+3，qi+2，qi+1（qi+3 > qi+2 > qi+1）
二栈：q1，q2，q3，q4……（size<k，q1 > q2 > q3）
一个合法的操作 qn，qn-1，q1，qn-2，qn-3，q2……