C. Уровни и регионы
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Радевуш играет в компьютерную игру, которая состоит из n уровней, пронумерованных от 1 до n. Уровни разбиты на k регионов (групп), каждый регион является непустым множеством последовательных уровней.

Игровой процесс состоит в повторении следующих действий:

  1. Если все уровни уже пройдены, то игра немедленно заканчивается. Иначе система определяет первый регион, в котором есть хотя бы один ещё не пройденный уровень. Обозначим этот регион за X.
  2. Создаётся пул для токенов. Каждый токен будет представлять один уровень, при этом несколько токенов могут представлять один и тот же уровень.
    • Для каждого уже пройденного уровня i из региона X система добавляет в пул ti токенов, которые будут представлять этот уровень.
    • Пусть 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. Проверяющая программа будет считать ваш ответ правильным, если .

Примеры
Входные данные
4 2
100 3 5 7
Выходные данные
5.7428571429
Входные данные
6 2
1 2 4 8 16 32
Выходные данные
8.5000000000
Примечание

В первом примере мы должны разбить 4 уровня на 2 региона. Оптимальным способом будет выделить первый уровень в первый регион, а три уровня со второго по четвёртый — во второй регион.

Во втором примере оптимально будет разбить уровни на 2 региона по 3 уровня в каждом.