CF643C.Levels and Regions

Radewoosh is playing a computer game. There are n levels, numbered 1 through n. Levels are divided into k regions (groups). Each region contains some positive number of consecutive levels.

The game repeats the the following process:

1. If all regions are beaten then the game ends immediately. Otherwise, the system finds the first region with at least one non-beaten level. Let X denote this region.
2. The system creates an empty bag for tokens. Each token will represent one level and there may be many tokens representing the same level.
   • For each already beaten level i in the region X, the system adds t__i tokens to the bag (tokens representing the i-th level).
   • Let j denote the first non-beaten level in the region X. The system adds t__j tokens to the bag.
3. Finally, the system takes a uniformly random token from the bag and a player starts the level represented by the token. A player spends one hour and beats the level, even if he has already beaten it in the past.

Given n, k and values _t_1, _t_2, ..., t__n, your task is to split levels into regions. Each level must belong to exactly one region, and each region must contain non-empty consecutive set of levels. What is the minimum possible expected number of hours required to finish the game?

拉德沃什正在玩一款电脑游戏。游戏中共有 $n$ 个关卡，编号为 $1$ 到 $n$。这些关卡被划分为 $k$ 个区域（组），每个区域包含若干个连续的关卡，且每个区域至少包含一个关卡。

游戏重复执行以下过程：

1. 若所有区域均已通关，则游戏立即结束；否则，系统找出第一个至少含有一个未通关关卡的区域。记该区域为 $X$。
2. 系统创建一个空的“令牌袋”。每个令牌代表一个关卡，同一个关卡可能对应多个令牌。
   • 对于区域 $X$ 中每一个已通关的关卡 $i$，系统向袋中加入 $t_i$ 个令牌（即代表第 $i$ 个关卡的 $t_i$ 个令牌）；
   • 设 $j$ 为区域 $X$ 中第一个未通关的关卡，则系统向袋中加入 $t_j$ 个令牌。
3. 最后，系统从袋中均匀随机抽取一个令牌，玩家随即开始挑战该令牌所代表的关卡。玩家花费一小时完成该关卡（即使此前已通关过该关卡，仍需再花一小时）。

给定 $n$、$k$ 及数值 $t_1,\,t_2,\,\dots,\,t_n$，你的任务是将 $n$ 个关卡划分为 $k$ 个区域。每个关卡必须恰好属于一个区域，且每个区域必须包含一个非空的连续关卡段。问：完成整个游戏所需的最小可能期望时间（以小时为单位） 是多少？

The first line of the input contains two integers n and k (1 ≤ n ≤ 200 000, 1 ≤ k ≤ min(50, n)) — the number of levels and the number of regions, respectively.

The second line contains n integers _t_1, _t_2, ..., t__n (1 ≤ t__i ≤ 100 000).

输入的第一行包含两个整数 $n$ 和 $k$（$1 ≤ n ≤ 200\,000$，$1 ≤ k ≤ \min(50, n)$）—— 分别表示关卡数量和区域数量。

第二行包含 $n$ 个整数 $t_1, t_2, ..., t_n$（$1 ≤ t_i ≤ 100\,000$）。

Print one real number — the minimum possible expected value of the number of hours spent to finish the game if levels are distributed between regions in the optimal way. Your answer will be considered correct if its absolute or relative error does not exceed 10 - 4.

Namely: let's assume that your answer is a, and the answer of the jury is b. The checker program will consider your answer correct if .

输出一个实数——在将关卡以最优方式分配到各个区域的前提下，完成游戏所需小时数的最小可能期望值。若你的答案绝对误差或相对误差不超过 $10^{-4}$，则视为正确。

具体而言：假设你的答案为 $a$，评测组的标准答案为 $b$。当满足 时，评测程序将判定你的答案正确。

In the first sample, we are supposed to split 4 levels into 2 regions. It's optimal to create the first region with only one level (it must be the first level). Then, the second region must contain other three levels.

In the second sample, it's optimal to split levels into two regions with 3 levels each.

在第一个样例中，我们需要将 4 个关卡划分为 2 个区域。最优方案是将第一个区域仅包含一个关卡（该关卡必须是第一个关卡），而第二个区域则必须包含其余三个关卡。

在第二个样例中，最优方案是将关卡划分为两个区域，每个区域各包含 3 个关卡。