Олимпиадный тренинг

Задача . B. Фишка и лента

Задача

Рассмотрим ленту, разделенную на \(n\) клеток, пронумерованных от \(1\) до \(n\) слева направо. Изначально в каждой клетке записано число \(0\).

Монокарп играет в игру с фишкой. Игра состоит из нескольких ходов. Во время первого хода Монокарп помещает фишку в \(1\)-ю клетку ленты. Во время каждого хода, за исключением первого, Монокарп выполняет ровно одно из двух следующих действий:

переместить фишку в следующую клетку (т. е. если фишка находится в клетке \(i\), то она перемещается в клетку \(i+1\)). Это действие невозможно, если фишка находится в последней клетке;
выбрать любую клетку \(x\) и телепортировать фишку в эту клетку. Можно выбрать ту же самую клетку, в которой сейчас находится фишка.

В конце каждого хода число, записанное в клетке с фишкой, увеличивается на \(1\).

Цель Монокарпа — сделать какое-то количество ходов так, чтобы в \(1\)-й клетке было записано число \(c_1\), во \(2\)-й клетке — число \(c_2\), ..., в \(n\)-й клетке — число \(c_n\). Он хочет телепортировать фишку как можно меньше раз.

Помогите Монокарпу вычислить минимальное количество раз, которое он должен телепортировать фишку.

Входные данные

В первой строке задано одно целое число \(t\) (\(1 \le t \le 10^4\)) — количество наборов входных данных.

Каждый набор входных данных состоит из двух строк:

в первой строке задано одно целое число \(n\) (\(1 \le n \le 2 \cdot 10^5\));
во второй строке заданы \(n\) целых чисел \(c_1, c_2, \dots, c_n\) (\(0 \le c_i \le 10^9\); \(c_1 \ge 1\)).

Можно доказать, что при таких ограничениях всегда можно за конечное число ходов добиться того, чтобы в клетках были записаны числа \(c_1, c_2, \dots, c_n\).

Дополнительное ограничение на входные данные: сумма значений \(n\) по всем наборам входных данных не превосходит \(2 \cdot 10^5\).

Выходные данные

Для каждого набора входных данных выведите одно целое число — минимальное количество раз, которое Монокарп должен телепортировать фишку.

Примечание

В первом наборе входных данных примера Monocarp может выполнять ходы следующим образом:

поместить фишку в \(1\)-ю клетку; числа в клетках равны \([1, 0, 0, 0]\);
переместить фишку в следующую (\(2\)-ю) клетку; числа в клетках равны \([1, 1, 0, 0]\);
переместить фишку в следующую (\(3\)-ю) клетку; числа в клетках равны \([1, 1, 1, 0]\);
телепортировать фишку в \(2\)-ю клетку; числа в клетках равны \([1, 2, 1, 0]\);
переместить фишку в следующую (\(3\)-ю) клетку; числа в клетках равны \([1, 2, 2, 0]\);
переместить фишку в следующую (\(4\)-ю) клетку; числа в клетках равны \([1, 2, 2, 1]\).

Примеры

№	Входные данные	Выходные данные
1	4 4 1 2 2 1 5 1 0 1 0 1 5 5 4 3 2 1 1 12	1 2 4 11

time 2000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам

	Кол-во
С++ Mingw-w64	3

Комментарий учителя

Ваш ответ

выберите язык и введите исходный код

Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!

Загруженные файлы

Нет