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