Pretty necklace#9408

Pretty necklace

2 secondi

128 megabyte

Media

Temirulan wants to make a necklace as a present to his beloved girl. A necklace is a cyclic sequence of blue and red colored beads.

Temirulan already has one that consists of $n$ beads. He knows that his girlfriend prefers red color over blue, so he decided to cut some subsequence of at least $k$ beads from the original necklace such that the ratio between red ones and the number of chosen beads will be maximized.

Can you help him to find this maximum ratio?

Input

The first line contains two integers $n$ , $k$ ( $1 \leq k \leq n \leq 5 \cdot 1 0^{5}$ 1 \le k \le n \le 5 \cdot 10^5) - the number of beads on the thread and lower-bound of beads for the new necklace.

The second line contains the sequence of $n$ integers separated by a single space $a_{i}$ a_i ( $0 \leq a_{i} \leq 1$ 0 \le a_i \le 1) - description of the original necklace.

$a_{i} = 0$ a_i = 0 corresponds to blue and $a_{i} = 1$ a_i = 1 corresponds to red color.

Esempi

Esempio 1

Loading

Esempio 2

Loading

Esempio 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