Background

In the 2015 cohort of a certain school, there are two OI top students, yyy and c01.

Problem Description

There are $N$ other students in the school besides them, and each student idolizes one of them. Now the teacher needs to assign them to dorm rooms. However, here is the issue:

For any dorm room, either everyone in it idolizes the same person, or the absolute difference between the numbers of students who idolize yyy and c01 in that room is at most $M$. Otherwise, they will start a fight.

To make things easier, the teacher makes the $N$ students stand in a line. Only people who stand consecutively can be placed into the same dorm room.

Assume each dorm room can hold arbitrarily many people. What is the minimum number of dorm rooms needed?

Input Format

The first line contains two positive integers $N$ and $M$.

Lines $2, 3, \cdots, N+1$ each contain one integer, $1$ or $2$. The number on line $i$ indicates, from left to right, the $(i-1)$-th person’s choice: $1$ means yyy, and $2$ means c01.

Output Format

One line with a single integer, the minimum number of dorm rooms needed.

5 1
1
1
2
2
1

1

Hint

Translated by ChatGPT 5