B. Фишка и лента
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Рассмотрим ленту, разделенную на $$$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$$$.

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

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

Пример
Входные данные
4
4
1 2 2 1
5
1 0 1 0 1
5
5 4 3 2 1
1
12
Выходные данные
1
2
4
11
Примечание

В первом наборе входных данных примера 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]$$$.