Марк убирает ряд из \(n\) комнат, \(i\)-я комната имеет неотрицательный уровень запыленности \(a_i\). У него есть волшебная чистящая машина, которая может выполнять следующую трехэтапную операцию:
- Марк выбирает два таких индекса \(i<j\), что уровни пыли \(a_i\), \(a_{i+1}\), \(\dots\), \(a_{j-1}\) строго больше \(0\).
- Машина изменяет \(a_i\) на новое значение \(a_i-1\).
- Машина изменяет \(a_j\) на новое значение \(a_j+1\).
Цель Марка — сделать \(a_1 = a_2 = \ldots = a_{n-1} = 0\), тогда он сможет перейти к уборке комнаты \(n\). Требуется определить минимальное количество операций, необходимых для достижения его цели.
Выходные данные
Для каждого набора входных данных выведите строку, содержащую одно целое число — минимальное количество операций. Можно доказать, что существует последовательность операций, удовлетворяющая требованию задачи.
Примечание
В первом наборе входных данных примера возможна следующая последовательность операций:
- выбрать \(i=1\) и \(j=2\), получить массив \([1,1,0]\);
- выбрать \(i=1\) и \(j=3\), получить массив \([0,1,1]\);
- выбрать \(i=2\) и \(j=3\), получить массив \([0,0,2]\).
После этого \(a_1=a_2=0\).
Во втором наборе входных данных примера возможна следующая последовательность операций:
- выбрать \(i=4\) и \(j=5\), получить массив \([0,2,0,1,1]\).
- выбрать \(i=2\) и \(j=3\), получить массив \([0,1,1,1,1]\).
- выбрать \(i=2\) и \(j=5\), получить массив \([0,0,1,1,2]\).
- выбрать \(i=3\) и \(j=5\), получить массив \([0,0,0,1,3]\).
- выбрать \(i=4\) и \(j=5\), получить массив \([0,0,0,0,4]\).
После пятой операции массив удовлетворяет требованиям задачи.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
3
2 0 0
5
0 2 0 2 0
6
2 0 3 0 4 6
4
0 0 0 10
|
3
5
11
0
|