Cute Ryan

Interview

Time limit1sMemory limit256 MB

Summary

Given a row of N dolls labeled 1 or 2, find the length of the shortest contiguous block containing at least K dolls labeled 1.

Level: Medium5 of 10
Topics: Two pointers, Sliding window, Array, Prefix sum
Solved: No attempts yet

Problem

$N$ dolls are placed in a row. Each doll is either a Ryan doll or an Apeach doll. A Ryan doll is written as 1 and an Apeach doll as 2. Find the length of the shortest contiguous block of dolls that contains at least $K$ Ryan dolls.

Input

The first line contains $N$ and $K$ . ( $1 \le K \le N \le 10^6$ )

The second line contains $N$ space-separated integers describing the dolls. Each value is 1 or 2.

Output

Print the length of the shortest contiguous block that contains at least $K$ Ryan dolls. If no such block exists, print -1.

Examples1

Example 1
Input
```
10 3
1 2 2 2 1 2 1 2 2 1
```
Expected output
```
6
```