B. Марк-уборщик
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Марк убирает ряд из $$$n$$$ комнат, $$$i$$$-я комната имеет неотрицательный уровень запыленности $$$a_i$$$. У него есть волшебная чистящая машина, которая может выполнять следующую трехэтапную операцию:

  • Марк выбирает два таких индекса $$$i<j$$$, что уровни пыли $$$a_i$$$, $$$a_{i+1}$$$, $$$\dots$$$, $$$a_{j-1}$$$ строго больше $$$0$$$.
  • Машина изменяет $$$a_i$$$ на новое значение $$$a_i-1$$$.
  • Машина изменяет $$$a_j$$$ на новое значение $$$a_j+1$$$.

Цель Марка — сделать $$$a_1 = a_2 = \ldots = a_{n-1} = 0$$$, тогда он сможет перейти к уборке комнаты $$$n$$$. Требуется определить минимальное количество операций, необходимых для достижения его цели.

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

Первая строка входных данных содержит одно целое число $$$t$$$ ($$$1\leq t\leq 10^4$$$) — количество наборов входных данных в тесте.

Первая строка каждого набора содержит одно целое число $$$n$$$ ($$$2\leq n\leq 2\cdot 10^5$$$) — количество комнат.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$0\leq a_i\leq 10^9$$$) — уровень пыли в каждой из комнат.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2\cdot 10^5$$$.

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

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

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

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

  • выбрать $$$i=1$$$ и $$$j=2$$$, получить массив $$$[1,1,0]$$$;
  • выбрать $$$i=1$$$ и $$$j=3$$$, получить массив $$$[0,1,1]$$$;
  • выбрать $$$i=2$$$ и $$$j=3$$$, получить массив $$$[0,0,2]$$$.

После этого $$$a_1=a_2=0$$$.

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

  • выбрать $$$i=4$$$ и $$$j=5$$$, получить массив $$$[0,2,0,1,1]$$$.
  • выбрать $$$i=2$$$ и $$$j=3$$$, получить массив $$$[0,1,1,1,1]$$$.
  • выбрать $$$i=2$$$ и $$$j=5$$$, получить массив $$$[0,0,1,1,2]$$$.
  • выбрать $$$i=3$$$ и $$$j=5$$$, получить массив $$$[0,0,0,1,3]$$$.
  • выбрать $$$i=4$$$ и $$$j=5$$$, получить массив $$$[0,0,0,0,4]$$$.

После пятой операции массив удовлетворяет требованиям задачи.