Рассмотрим ленту, разделенную на $$$n$$$ клеток, пронумерованных от $$$1$$$ до $$$n$$$ слева направо. Изначально в каждой клетке записано число $$$0$$$.
Монокарп играет в игру с фишкой. Игра состоит из нескольких ходов. Во время первого хода Монокарп помещает фишку в $$$1$$$-ю клетку ленты. Во время каждого хода, за исключением первого, Монокарп выполняет ровно одно из двух следующих действий:
В конце каждого хода число, записанное в клетке с фишкой, увеличивается на $$$1$$$.
Цель Монокарпа — сделать какое-то количество ходов так, чтобы в $$$1$$$-й клетке было записано число $$$c_1$$$, во $$$2$$$-й клетке — число $$$c_2$$$, ..., в $$$n$$$-й клетке — число $$$c_n$$$. Он хочет телепортировать фишку как можно меньше раз.
Помогите Монокарпу вычислить минимальное количество раз, которое он должен телепортировать фишку.
В первой строке задано одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.
Каждый набор входных данных состоит из двух строк:
Можно доказать, что при таких ограничениях всегда можно за конечное число ходов добиться того, чтобы в клетках были записаны числа $$$c_1, c_2, \dots, c_n$$$.
Дополнительное ограничение на входные данные: сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.
Для каждого набора входных данных выведите одно целое число — минимальное количество раз, которое Монокарп должен телепортировать фишку.
441 2 2 151 0 1 0 155 4 3 2 1112
1 2 4 11
В первом наборе входных данных примера Monocarp может выполнять ходы следующим образом:
Название |
---|