Description

There are many top students… of course… each student has someone they sincerely admire.

At a certain school there are two top students, A and B. The newly enrolled $n$ students have already heard of their legends, so each student already sincerely worships one of them. Now the teacher needs to assign them to computer labs. For each lab, either everyone in that lab worships the same top student, or the absolute difference between the counts of the two worshippers does not exceed $m$.

The $n$ students stand in a line, and the teacher will only assign a contiguous segment of students to the same lab. The teacher wants to know the minimum number of labs needed.

Input Format

The first line contains two integers $n$ and $m$.

Lines $2$ through $(n + 1)$ each contain an integer, either $1$ or $2$. The integer on line $(i + 1)$ indicates whom the $i$-th student worships: $1$ means A, $2$ means B.

Output Format

Output a single integer, the minimum number of labs required.

5 1
2
2
1
2
2

2

Hint

Constraints

• For $30\%$ of the testdata, it is guaranteed that $1 \le n \le 50$, $0 \le m \le 50$.
• For $100\%$ of the testdata, it is guaranteed that $1 \le n \le 2500$, $0 \le m \le 2500$.

Translated by ChatGPT 5