Красивое ожерелье
Темирулан хочет сделать ожерелье в подарок своей любимой девушке. Ожерелье - это циклическая последовательность синих и красных бусин.
У Темирулана уже есть ожерелье, состоящее из n бусинок. Он знает, что его подруга предпочитает красный цвет голубому, поэтому он решил вырезать некоторую подпоследовательность из не менее k бусинок из оригинального ожерелья так, чтобы соотношение между красными и количеством выбранных бусинок было максимальным.
Можете ли Вы помочь ему найти это максимальное соотношение?
Входные данные
Первая строка содержит два целых числа n и k (1 ≤ k ≤ n ≤ 5 * 10^5) - число бусинок на нити и минимальная граница числа бусинок в новом ожерельи.
Вторая строка содержит последовательность из n целых чисел a[i] (0 ≤ a[i] ≤ 1) - описание исходного ожерелья.
a[i] = 0 соответствует голубому цвету, a[i] = 1 соответствует красному цвету.