Как известно, чтобы победить лорда Волан-де-Морта, Гарри необходимо сперва уничтожить все крестражи. Последний крестраж лорда Сами-Знаете-кого представляет собой массив \(a\) состоящий из \(n\) целых чисел, который Гарри необходимо уничтожить. Массив считается уничтоженным, если все его элементы равны 0. Чтобы его уничтожить, Гарри может производить два типа операций:
- выбрать индекс \(i\) (\(1 \le i \le n\)), целое число \(x\) и вычесть из \(a_i\) число \(x\).
- выбрать индексы \(i\) и \(j\) (\(1 \le i, j \le n; i \ne j\)), целое число \(x\) и вычесть из \(a_i\) число \(x\), а из \(a_j\) — число \(x + 1\).
Обратите внимание, что \(x\) может быть произвольным, в том числе и отрицательным.
У Гарри осталось совсем немного времени. Помогите ему и узнайте, какое минимальное число операций с массивом ему придётся совершить, чтобы уничтожить массив и покончить с лордом Волан-де-Мортом!
Выходные данные
Выведите одно число — минимальное количество действий, за которое Гарри сможет уничтожить массив \(a\).
Примечание
В первом примере можно три раза применить операцию первого типа к массиву.
Во втором примере можно два раза применить операцию второго типа: сначала выбрать \(i = 2, j = 1, x = 4\) и получить массив \((0, -1, -2)\), затем выбрать \(i = 3, j = 2, x = -2\) чтобы уничтожить массив.
В третьем примере ничего делать не надо, так как массив уже состоит из нулей.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1 10 100
|
3
|
|
2
|
3
5 3 -2
|
2
|
|
3
|
1
0
|
0
|