Налийте якомога швидше

Обмеження: 2 сек., 256 МіБ

На барній стійці послідовно стоять \(n\) кубків. Спочатку вони всі пусті, але нам відомо, що в \(i\)-тий кубок необхідно налити рівно \(a_i\) грам рідини. За одну секунду бармен може вибрати неперервний проміжок кубків і або налити в кожен з них по одному граму або налити в кожен з них по \(x\) грамів. Виливати рідину з кубка строго заборонено. Вас цікавить за який найменший проміжок часу бармен може виконати замовлення.

Вхідні дані

У першому рядку знаходяться два цілих числа: \(n\) та \(x\). В наступному рядку дано \(n\) цілих чисел \(a_i\).

Вихідні дані

У єдиному рядку виведіть одне ціле число — мінімальну кількість секунд необхідну для наповнення усіх кубків.

Обмеження

\(1 \le n \le 300000\),

\(1 \le x, a_i \le 10^9\).

Приклади