Roller Coaster 2

JAG (Japan Amusement Group) is a popular amusement park that attracts many tourists. Its roller coaster is the most popular attraction.

Today the park is crowded, and many group guests are waiting in line in front of the roller coaster. As a staff member, you check the line. There are currently $N$ groups in the waiting line, and the $i$-th group from the front has $a_i$ people.

The roller coaster can carry up to $M$ people in one run. For each run, you seat guests by the following rules, and you repeat this until the waiting line is empty.

1. If the line is empty, or if the group at the front has more people than the number of empty seats, the coaster departs and this run ends.
2. Otherwise, seat all people in the front group in the empty seats.
3. Return to step 1.

You notice that the park is about to close. You consider whether swapping the order of one pair of adjacent groups can reduce the number of runs. Specifically, you may perform the following operation at most once.

Choose an integer $i$ with $1 \le i \le N-1$, and swap the $i$-th and $(i+1)$-th groups in the waiting line.

If you perform the operation optimally, what is the minimum number of runs needed to empty the waiting line? No new guests join the line, and no waiting guests leave it.

The first line contains integers $N$ and $M$. $N$ is the number of waiting groups, with $2 \le N \le 2 \times 10^5$. $M$ is the maximum number of people who can ride in one run, with $1 \le M \le 10^9$.

The second line contains $N$ integers $a_1, a_2, \ldots, a_N$, with $1 \le a_i \le M$.

The sum of $N$ over all datasets does not exceed $2 \times 10^6$. The input contains at most 50 datasets and ends with a line containing two zeros.

For each dataset, print on one line the minimum number of runs needed when the operation is performed optimally.