| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 32 | 6 | 6 | 85.714% |
Фирма <<Kel-Morian Productions>> разрабатывают искусственный интеллект для новой автоматизированной модели промышленного робота SCV-2. На данном этапе создается робот для строительства и ремонта стен, составленных из стандартных строительных блоков.
Для начала было принято решение сделать упрощенную модель робота, который будет работать со стенами, состоящими из блоков одинакового размера. Стена представляет собой последовательность столбиков, составленных из блоков, пример такой стены приведен на рисунке 1.
Рисунок 1
Первая модель робота может выполнять ровно одно элементарное действие --- взять верхний блок в некотором столбике и положить его на соседний столбик. При этом создавать новый столбик, ставя блок рядом с краем стены, не разрешается.
В качестве тестового задания для искусственного интеллекта была поставлена задача выравнивания стены. Стена называется ровной, если высота двух любых столбиков различается не более чем на один. В процессе выравнивания робот должен с использованием элементарных действий превратить заданную стену в произвольную ровную. При этом количество выполненных элементарных действий должно быть минимально, а количество столбиков в стене не должно измениться.
Например, стена, приведенная на рисунке 1, может быть превращена в ровную стену, приведенную на рисунке 2, за четыре элементарных действия, и это число действий является минимальным для данной стены.
Рисунок 2
Помогите разработчикам искусственного интеллекта проверить разработанный ими алгоритм, найдите минимальное количество действий, которое придется совершить роботу для выравнивания заданной стены.
В первой строке входного файла записано целое число $n$ (1ドル \le n \le 1000$) --- количество вертикальных рядов, из которых состоит стена. Вторая строка содержит числа $a_1, a_2, \ldots, a_n,ドル где $a_i$ задает количество блоков в $i$-м столбике (1ドル \le a_i \le 10^6$).
В выходной файл выведите единственное целое число --- минимальное количество перемещений блоков, необходимое для выравнивания стены.
8 1 2 4 1 3 4 1 2
4