Let us add Chair \(0\) at the left end and Chair \(N+1\) at the right end. We see these chairs as marked.

Let \(f(l,r)\) be the expected number of chairs - considering only the \(l\)-th through \(r\)-th chairs from the left - that will get marked from now on when the \(l\)-th and \(r\)-th chairs are already marked, but the others are not. The answer we should find is \(f(1, N+2)\).

If we have no nice chairs here, \(f(l,r)=0\). Otherwise, it is \(1+\sum_{i=1}^{k} (f(l,s_i)+f(s_i,r))/k\), where the nice chairs are Chairs \(s_1, s_2, \ldots, s_k\).

We can find \(f\) in \(O(N^3)\) time with DP on segments, but it would be too slow. Let us consider separately finding \(\sum_{i=1}^{k}f(l,s\_i)\) and \(\sum_{i=1}^{k}f(s_{i},r)\). Then, what we need to do is to find the sum of \(f(l,j)\) and that of \(f(j,r)\) over \(j\) such that \(l < j < r, a_{l} < a_{j} < a_{r}\). We can do it in \(O(\log N)\) time with Fenwick Tree or Segment Tree.

We can do the whole process in \(O(N^2 \log N)\) time, which is fast enough.