Красиве намисто#9408

Красиве намисто

2 секунди

128 мегабайтів

Середня

Темирулан хоче зробити намисто в подарунок своїй коханій дівчині. Намисто - це циклічна послідовність синіх і червоних намистин.

У Темирулана вже є намисто, що складається з $n$ намистин. Він знає, що його подруга надає перевагу червоному кольору перед синім, тому він вирішив вирізати деяку підпослідовність з не менше ніж $k$ намистин з оригінального намиста так, щоб співвідношення між червоними і кількістю вибраних намистин було максимальним.

Чи можете ви допомогти йому знайти це максимальне співвідношення?

Вхідні дані

Перший рядок містить два цілих числа $n$ і $k$ ( $1 \leq k \leq n \leq 5 \cdot 1 0^{5}$ 1 \le k \le n \le 5 \cdot 10^5) - кількість намистин на нитці та мінімальна кількість намистин у новому намисті.

Другий рядок містить послідовність з $n$ цілих чисел $a_{i}$ a_i ( $0 \leq a_{i} \leq 1$ 0 \le a_i \le 1) - опис вихідного намиста.

$a_{i} = 0$ a_i = 0 відповідає синьому кольору, $a_{i} = 1$ a_i = 1 відповідає червоному кольору.

Приклади

Приклад 1

Loading

Приклад 2

Loading

Приклад 3

Loading

1 \leq k \leq n \leq 5 \cdot 1 0^{5}

a_{i}

0 \leq a_{i} \leq 1

a_{i} = 0

a_{i} = 1