제트코스터 2

JAG(Japan Amusement Group)는 관광객이 많이 찾는 국내 유명 놀이공원이다. 그중 제트코스터는 가장 인기 있는 놀이기구다.

오늘도 JAG는 손님으로 붐비고, 제트코스터 앞에는 여러 단체 손님이 줄을 서서 기다리고 있다. 직원인 당신이 확인해 보니 대기 줄에는 현재 $N$개의 단체가 있으며, 줄 맨 앞에서 $i$번째 단체는 $a_i$명이다.

제트코스터는 한 번 운행할 때 최대 $M$명까지 태울 수 있다. 각 운행마다 다음 규칙에 따라 손님을 좌석으로 안내하고, 대기 줄에 손님이 없을 때까지 이를 반복한다.

1. 대기 줄이 비었거나, 맨 앞 단체의 인원이 빈 좌석 수보다 많으면 발차하고 이번 운행을 마친다.
2. 그렇지 않으면 맨 앞 단체 전원을 빈 좌석에 앉힌다.
3. 1로 돌아간다.

폐장 시간이 가까워졌음을 알게 된 당신은, 인접한 두 단체의 순서를 서로 바꾸면 운행 횟수를 줄일 수 있지 않을지 생각한다. 구체적으로는 다음 연산을 최대 1회 할 수 있다.

$1 \le i \le N-1$을 만족하는 정수 $i$를 하나 고르고, 대기 줄 맨 앞에서 $i$번째 단체와 $i+1$번째 단체의 순서를 바꾼다.

연산을 최적으로 했을 때, 대기 줄을 모두 비우는 데 필요한 운행 횟수의 최솟값은 얼마인가? 새 손님이 줄에 추가되지 않고, 줄에 있던 손님이 빠지지도 않는다고 가정한다.

첫째 줄에 정수 $N$, $M$이 주어진다. $N$은 대기 단체의 수이며 $2 \le N \le 2 \times 10^5$이다. $M$은 한 번의 운행에 탑승할 수 있는 최대 인원이며 $1 \le M \le 10^9$이다.

둘째 줄에 정수 $a_1, a_2, \ldots, a_N$이 주어지며 $1 \le a_i \le M$이다.

모든 데이터셋의 $N$ 합은 $2 \times 10^6$을 넘지 않는다. 데이터셋은 최대 50개이며, 0 두 개가 적힌 줄로 입력이 끝난다.

각 데이터셋에 대해 연산을 최적으로 했을 때 필요한 운행 횟수의 최솟값을 한 줄에 출력한다.