D. Лестница
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Рассмотрим лестницу, состоящую из $$$n$$$ ступеней. Каждая ступень может быть целой или сломанной. Для каждой сломанной ступени задано целое число $$$a_i$$$, обозначающее сложность ее ремонта.

Каждый день вы можете:

  • либо отремонтировать произвольную сломанную ступеньку. Усилия, необходимые для ремонта $$$i$$$-й ступени, равны $$$a_i$$$;
  • либо отремонтировать две смежные сломанные ступеньки. Усилия, необходимые для ремонта $$$i$$$-й и $$$(i+1)$$$-й ступени, равны $$$2 \cdot (a_i+a_{i+1})$$$.

Вы хотите отремонтировать все сломанные ступени лестницы и сделать это за минимальное количество дней. Каково минимальное общее усилие, необходимое для ремонта всех сломанных ступеней за минимальное количество дней?

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

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

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

  • первая строка содержит одно целое число $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — количество ступеней;
  • вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^8$$$). Если $$$a_i = 0$$$, то $$$i$$$-я ступень не нуждается в ремонте; в противном случае $$$i$$$-я ступень сломана, и $$$a_i$$$ — сложность ее ремонта.

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

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

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

Пример
Входные данные
6
5
0 0 0 0 0
4
0 13 15 8
4
13 15 0 8
8
1 2 3 4 5 6 7 8
5
99999999 100000000 99999999 99999999 99999999
5
2 3 4 3 2
Выходные данные
0
59
64
72
899999993
24
Примечание

В первом наборе входных данных вам ничего не нужно делать.

Во втором наборе входных данных вы можете отремонтировать $$$3$$$-ю и $$$4$$$-ю ступени в первый день, и $$$2$$$-ю ступень во второй день. Общее усилие будет равно $$$2 \cdot (15 + 8) + 13 = 59$$$.

В третьем наборе входных данных вы можете отремонтировать $$$4$$$-ю ступень в первый день, и две первые ступени во второй день. Общее усилие будет равно $$$8 + 2 \cdot (13 + 15) = 64$$$.