题意
有(n)个人按顺序站成一排，每个人手里都有一张写有数字的牌（构造(1sim n)的排列）。
初始牌都是未知的，甚至连每个人都不知道自己手里的牌。
他们在玩游戏，从前往后按顺序，选择
（1）翻开自己的牌，公之于众。
（2）选择一位前面在场的人，拿走他的牌离场，那个人继承这个人的牌，翻开并公之于众。
每个人都绝顶聪明，希望最后自己手里的牌最大。
令(E(p))为期望情况下，最后未离开的人数。
令(S_1[n]=sumlimits_{p=1}^N E(p)).
有(S_k[n]=sumlimits_{p=1}^N S_{k-1}[p])（(k>1)）
做法
定义1：对于每个人，他知道的信息是前面手里有牌的人的牌的数字（记为集合(P)），以及这个人及后面的人手里的牌的数字集合（记为集合(R)）。
定义2：对于一个集合(S)，令(max S)为集合内的最大元素，特殊的(S=-infty)，则(max S=0)；令(min S)为集合内的最小元素，特殊的(S=empty)，则(min S=+infty)。
大体的策略为，根据场上所剩人数，以及(max P)与(min R)，考虑是否拿走(max P)，或者翻开。
结论1：若(min R>max P)，则翻开。
证明显然
若(min R<max P)，翻开，则可能面临这张牌特别小，或者这张牌很大但可能会被后面的人换走；选择操作二，则直接获得(max P)的收益。
在阐述我们的结论前，先给出一些定义。
定义3：对于未离场的人，手里的牌的相对大小，称为这些人的排位。
定义4：若经过一个人的决策，前面在场的人的排位发生变化，或者(min R>max P)，则称这次决策为关键决策。
接下来，证明一个跟结论1对立的，很强的结论。
结论2：若(min R<max P)，会换掉(max P)带走。
证明：
考虑对从后往前的人的决策施归纳，假设当前的人之后的每个人都会按结论1和结论2操作（边界情况易证）。
当前这个人面临，(min R<max P)。
反证法，假设我们翻开这张牌，最终的收益会大于(max P)。
有两种情况，（1）"这张牌大于(max P)"（2）"这张牌小于(max P)"
先证明（2）
（2）"这张牌小于(max P)"：
引理1：若目前(min R<max P)，对于当前的(max P_{nw})，在下一个关键决策后，(max P_{nxt}<max P_{nw})。
证明引理1，在关键决策前，由于均满足(max P<min R)，且排位关系没有发生变化，每次我们都在换同一个人的牌。
若这次关键决策，是由排位发生变化触发的，那么当前的人手里的牌小于(P)中的次大值，那么(max P_{nxt})等于原(P)的次大值，显然满足(max P_{nxt}<max P_{nw})。
若这次关键决策，是由(max P<min R)触发的，原本满足(max P>min R)，那么这个人手里的牌恰好是(min R)（否则不会改变不等式关系），因为每次都在换同一个人牌，现在的(max P_{nxt})等于(max {P_{nw}-{max P_{nw}}+min R_{nw}}<max P_{nw})。
引理1得证。
引理2：若目前(min R<max P)，必然存在下一个关键决策。
证明引理2，考虑反证，假设之后排位一直不会发生改变，由于此时(min R<max P)，则(P eq empty)，最后一个人操作后，(R=empty)，则(min R'=+infty>max P)，这是一次关键决策。
引理2得证。
这张牌小于(max P)，如果想获得大于(max P)的收益，那么必定得等某一时刻(max P'=)这张牌，然后在某次交换后，这个人手里的牌变大，但根据引理1，(P)集合内的最大值会在关键决策后严格变小，再根据引理2，容易知道最终这个人手里的牌不会变大。
故无论如何，这个人的收益会小于(max P)，与假设矛盾。
再证明（1）
（1）"这张牌大于(max P)"
这张牌成为(max P)，下次关键决策后，(max P_{nxt}<max P_{nw})，这张牌也会被换走。
故无论如何，这个人的收益会小于(max P)，与假设矛盾。
得证。
根据结论1与结论2，最终留下来的人均为后缀
结论3：对于一个给定的(n)阶排列，一个数最终保留下来当且仅当其为后缀最小值。
证明：
首先在一个人操作后，其手里那张牌必定会在场上。
引理：假设一个数(v)不为后缀最小值，令其位置为(x)，那么第(x+1)个人会将其替换。
证明引理，考虑对位置从小到大施归纳，
因为(v)不为后缀最小值，显然第(x+1)个人会选择带走(max P)
我们假设当前(max P eq v)，即(max P>v)，显然(max P)不为后缀最小值，根据归纳，其已被删除，与假设矛盾。
引理得证
那么现在只需要证明任意后缀最小值(x)不会被删除，一个数字被删除，当且仅当其成为(max P)，当(x)成为(max P)，由于其为后缀最小值，此时(min R>max P)，后面的人会选择翻开牌而不是替换掉(x)。
得证。
那么(E(p)=E(后缀最小值个数)=sumlimits_{i=1}^n frac{1}{i})。
(S_0(x)=H(x)=sumlimits_{i=1}^{infty}(sumlimits_{j=1}^i frac{1}{j})x^i=sumlimits_{j=1}^{infty} frac{1}{j}frac{x^j}{1-x}=frac{-ln(1-x)}{1-x})
那么(S_k(x)=S_{k-1}cdot frac{1}{1-x}=frac{-ln(1-x)}{(1-x)^{k+1}})
如何快速计算(S_k(x))的某一项呢？
((S_k[n]x^n)'=nS_k[n]x^{n-1}={n+kchoose k+1}x^{n-1}+(k+1)S_{k+1}(n-1)x^{n-1})
故有(n imes S_k[n]=(k+1)S_{k+1}[n-1]+{n+kchoose k+1})
整理一下：(S_{k+1}[n]=frac{n+1}{k+1}S_k[n+1]-frac{{n+ k+1choose k+1}}{k+1})
然后只需要考虑计算调和级数了。
较小时暴力，较大时转为简单形式+收敛级数：( ext{ln}(n)+gamma+frac{1}{2n})
其中(gamma)为欧拉常数，可以通过公式计算：