Splitting Game Levels

Areum plays a computer game with $n$ levels, numbered $1$ through $n$.

The $n$ levels are split into $k$ groups. Each group consists of consecutive levels, every level belongs to exactly one group, and no group is empty.

The game repeats the following process.

1. If every level is cleared, the game ends. Otherwise the system finds the first group that still has at least one uncleared level. Call this group $X$.
2. The system prepares an empty bag for coins. One coin represents one level, and several coins may represent the same level.
   • For every already cleared level $i$ in group $X$, the system puts $t_i$ coins representing level $i$ into the bag.
   • Let $j$ be the first uncleared level in group $X$. The system puts $t_j$ coins representing level $j$ into the bag.
3. The system picks one coin from the bag uniformly at random and tells Areum the level that coin represents. Areum plays that level for one hour and always clears it. If the level was already cleared, the hour is still spent and nothing about the cleared levels changes.

The expected time until the game ends depends on how the levels are split. Given $n$, $k$ and $t_1, t_2, \dots, t_n$, write a program that computes the expected time for a split that makes it as small as possible.

The first line contains $n$ and $k$. ($1 \le n \le 200\,000$, $1 \le k \le \min(50, n)$)

The second line contains $t_1, t_2, \dots, t_n$. ($1 \le t_i \le 100\,000$)

Print the smallest expected time on one line, rounded to six digits after the decimal point. Pad with zeros so that six digits always follow the decimal point.

In the first example, putting level $1$ in one group and the remaining levels in the other group is optimal.

In the second example, splitting the levels into two groups of three is optimal.