左端にイス \(0\) を、右端にイス \(N+1\) を追加します。イス \(0,N+1\) には印がついていることにします。

\(f(l,r)\) を左から \(l\) 番目から \(r\) 番目までのイスにのみ着目し、印がついているイスが \(l\) 番目と \(r\) 番目のイスのとき、最終的に両端のイス以外で印をつけられるイスの個数の期待値、とします。求めるべき答えは \(f(1,N+2)\) です。

現在良いイスがないなら、\(f(l,r)=0\) です。 それ以外の場合、良いイスの位置を \(s_1, s_2, \ldots, s_k\) として \(1+\sum_{i=1}^{k} (f(l,s_i)+f(s_i,r))/k\) です。

\(f\) は区間DPにより \(O(N^3)\) で求めることができますが実行時間制限には間に合いません。\(\sum_{i=1}^{k}f(l,s_i)\) と \(\sum_{i=1}^{k}f(s_{i},r)\) を別々に求めることを考えると、\(l < j < r, a_{l} < a_{j} < a_{r}\) を満たす \(j\) について \(f(l,j)\), \(f(j,r)\) の総和が求められればよいことがわかります。これはFenwick Tree や Segment Tree を用いて \(O(\log N)\) で求めることができます。

全体として、\(O(N^2 \log N)\) で実行可能で十分高速です。