Чтобы подготовить своих осьминогов «Такодачи» к правлению миром, Ниномае Ина-нис, также известная как Ина с Горы, приказала Хишимачи Суйсей бросать в них валуны. Ина просит вас, Кирю Коко, помочь выбрать, как именно бросать валуны.
В одну линию на горе Ины находятся \(n\) осьминогов, они пронумерованы \(1, 2, \ldots, n\). \(i\)-й осьминог изначально имеет здоровье, равное \(a_i\), где \(1 \leq a_i \leq k\).
Каждый валун падает на последовательных осьминогов с номерами \(l, l+1, \ldots, r\), где \(1 \leq l \leq r \leq n\). Вы можете выбрать числа \(l\) и \(r\) для каждого валуна произвольным образом.
Каждый валун уменьшает здоровье каждого осьминога, на которого он падает, на \(1\). Однако осьминоги бессмертны, поэтому как только здоровье осьминога становится равно \(0\), он немедленно восстановит свое здоровье до \(k\).
По данным значениям начального здоровья осьминогов определите минимальное количество валунов, необходимых для того, чтобы здоровье всех осьминогов стало равно \(k\).
Выходные данные
Для каждого набора входных данных выведите минимальное количество валунов, которое необходимо бросить, чтобы значения здоровья всех осьминогов стали равными \(k\).
Примечание
В первом наборе входных данных минимальное количество бросков валуна равно \(2\):
- Бросить первый валун между \([l,r] = [1,3]\). Тогда значения здоровья осьминогов станут \([3, 1, 3, 3]\).
- Бросить второй валун между \([l,r] = [2,2]\). Тогда значения здоровья осьминогов станут \([3, 3, 3, 3]\).
Во втором наборе минимальное количество бросков валуна равно \(4\). Диапазоны \([l,r]\) равны \([1,7], [2, 6], [3, 5], [4, 4]\).