P2418 yyy loves OI IV

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

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?

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.

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

| Test point ID | Range of $N$ | Range of $M$ | | :-----------: | :-----------: | :-----------: | | $1 \sim 3$ | $\le 2500$ | $\le 10$ | | $4 \sim 5$ | $\le 5\times 10 ^ 5$ | $\le 10$ | | $6 \sim 10$ | $\le 5\times 10 ^ 5$ | $\le 2000$ | Translated by ChatGPT 5