C. Помогаем природе
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Маленький Леон живет в лесу. Недавно он заметил, что некоторые деревья возле его любимой тропинки засыхают, а другие наоборот слишком увлажнены. Леон очень любит свой лес, поэтому решил научиться контролировать уровень влажности почвы, чтобы спасти деревья.

Возле тропинки растут $$$n$$$ деревьев, текущие уровни влажности которых заданы массивом $$$a_1, a_2, \dots, a_n$$$. Леон научился трем способностям, которые помогут ему осушать и поливать почву.

  • Выбрать позицию $$$i$$$ и уменьшить уровень влажности деревьев $$$1, 2, \dots, i$$$ на $$$1$$$.
  • Выбрать позицию $$$i$$$ и уменьшить уровень влажности деревьев $$$i, i + 1, \dots, n$$$ на $$$1$$$.
  • Увеличить уровень влажности всех деревьев на $$$1$$$.

Леон хочет узнать минимальное число действий, которое необходимо совершить, чтобы каждое дерево имело уровень влажности равный $$$0$$$.

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

Первая строка теста содержит одно целое число $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$)  — количество наборов входных данных. Затем следуют $$$t$$$ наборов входных данных.

В первой строке каждого набора входных данных вводится одно целое число $$$n$$$ ($$$1 \leq n \leq 200\,000$$$).

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

Сумма значений $$$n$$$ по всем наборам тестовых данных не превосходит $$$200\,000$$$.

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

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

Пример
Входные данные
4
3
-2 -2 -2
3
10 4 7
4
4 -4 4 -4
5
1 -2 3 -4 5
Выходные данные
2
13
36
33
Примечание

В первом наборе входных данных достаточно $$$2$$$ раза применить операцию прибавления $$$1$$$ ко всему массиву.

Во втором наборе входных данных можно $$$4$$$ раза применить операцию вычитания на префиксе длины $$$3$$$ и получить массив $$$6, 0, 3$$$.

После этого $$$6$$$ раз применить операцию вычитания на префиксе длины $$$1$$$ и $$$3$$$ раза операцию вычитания на суффиксе длины $$$1$$$. Итого, количество действий составит $$$4 + 6 + 3 = 13$$$. Можно показать, что меньшим количеством действий обойтись нельзя, поэтому $$$13$$$ — это ответ.