Radewoosh 正在玩电脑游戏。有 n 个级别,编号为 1 到 n。级别分为 k 个区域(组)。每个区域包含一些正数的连续级别。
游戏重复以下过程:
1. 如果所有地区都被击败,则游戏立即结束。否则,系统找到具有至少一个不败级别的第一区域。让 X 表示该区域。
2. 系统创建一个空的代币袋。每个令牌代表一个级别,并且可能有多个令牌代表同一级别。 对于区域 X 中每个已击败的关卡 i,系统都会将 ti 代币添加到袋子中(代表第 i 关的代币)。 让 j 表示区域 X 中的第一个未击败级别。系统将 tj 个代币添加到袋子中。
3. 最后,系统从袋子中取出一个均匀随机的代币,玩家开始该代币所代表的关卡。玩家花费一小时来通关,即使他过去已经通关过。
给定 n、k 和值 t1、t2、...、tn,您的任务是将级别划分为区域。每个级别必须恰好属于一个区域,并且每个区域必须包含非空的连续级别集。完成游戏所需的最少预期小时数是多少?
输入
输入的第一行包含两个整数 n 和 k (1 ≤ n ≤ 200 000, 1 ≤ k ≤ min(50, n)) - 分别是级别数和区域数。
第二行包含 n 个整数 t1, t2, ..., tn (1 ≤ ti ≤ 100 000)。
输出
打印一个实数 - 如果关卡以最佳方式分布在区域之间,完成游戏所花费的小时数的最小可能预期值。如果您的答案的绝对或相对误差不超过 10 - 4,则视为正确。
即:假设你的答案是a,陪审团的答案是b。如果 $$\frac{|a-b|}{\max(1,b)} \leq 10^{-4}$$,检查程序将认为您的答案正确。
示例
输入 #1
4 2 100 3 5 7
输出 #1
5.7428571429
输入 #2
6 2 1 2 4 8 16 32
输出 #2
8.5000000000
注意
在第一个示例中,我们应该将 4 个级别分为 2 个区域。最好创建只有一个级别的第一个区域(它必须是第一个级别)。然后,第二个区域必须包含其他三个级别。
在第二个示例中,最好将级别分为两个区域,每个区域有 3 个级别。