eolymp
bolt
Try our new interface for solving problems
Problems

Экзамен

Экзамен

Time limit 2 seconds
Memory limit 256 MiB

Мария Петровна работает преподавателем в университете. В середине семестра она дала своим студентам контрольную работу, в которой было n заданий, упорядоченных по возрастанию сложности.

Мария Петровна знает, что каждый из её студентов относится к одной из трёх категорий:

  • Трудолюбивый студент решает на контрольной задачи в порядке увеличения сложности, начиная с самой лёгкой, и не пропуская ни одной задачи, пока не закончится время контрольной.

  • Умный студент решает на контрольной задачи в порядке уменьшения сложности, начиная с самой сложной, и не пропуская ни одной задачи, также пока не закончится время контрольной.

  • Плохой студент списывает ровно одну задачу у какого-либо трудолюбивого или умного студента. При этом, два плохих студента не могут списать одну и ту же задачу у одного и того же человека.

Трудолюбивые и умные студенты всегда правильно решают все задачи, которые успевают.

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

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

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

Input data

Входной файл содержит несколько тестов. В первой строке входного файла содержится целое число T — число тестов. Далее следуют описания тестов.

Описание каждого теста состоит из двух строк. В первой строке описания задано целое число n — количество заданий в контрольной работе. Далее для каждого задания, в порядке возрастания сложности, указано число a_i — количество студентов, которым зачтена соответствующая задача (0a_i10^9).

Гарантируется, что суммарное число заданий во всех тестах не превосходит 10^5, а также то, что в контрольной была хотя бы одна задача.

Output data

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

Пояснение к примерам

В первом тесте у Марии Петровны могло быть три трудолюбивых студента, два из которых решили по две задачи, а один — только одну, и еще один умный студент, который решил самую сложную задачу (но ничего больше решить не успел).

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

Examples

Input example #1
2
4
3 2 0 1
3
1 5 1
Output example #1
0
3
Source XIII All-Russian Olympiad schoolchildren team programming