| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 512 MB | 10 | 1 | 1 | 100.000% |
Мария Петровна работает преподавателем в университете. В середине семестра она дала своим студентам контрольную работу, в которой было $n$ заданий, упорядоченных по возрастанию сложности.
Мария Петровна знает, что каждый из ее студентов относится к одной из трех категорий:
Трудолюбивые и умные студенты всегда правильно решают все задачи, которые успевают.
Мария Петровна очень не любит студентов, которые списывают. Поэтому, если она узнает, что кто-то у кого-то списал, то обоим студентам она эту задачу не засчитывает. По итогам контрольной Мария Петровна внесла в ведомость зачтенные задачи для каждого студента и про каждую задачу посчитала, скольким студентам она ее зачла.
Поскольку приближаются экзамены, Мария Петровна решила оценить число плохих студентов в группе, чтобы спланировать время на пересдачи. К сожалению, она потеряла ведомость с зачтенными задачами и сохранила лишь листок, в котором записано для каждой задачи, какому числу студентов эта задача зачтена.
Мария Петровна интересуется, какое минимальное число плохих студентов может быть в группе. Помогите ей это выяснить.
Входной файл содержит несколько тестов. В первой строке входного файла содержится целое число $T$ --- число тестов. Далее следуют описания тестов.
Описание каждого теста состоит из двух строк. В первой строке описания задано целое число $n$ --- количество заданий в контрольной работе. Далее для каждого задания, в порядке возрастания сложности, указано число $a_i$ --- количество студентов, которым зачтена соответствующая задача ($0 \le a_i \le 10^9$).
Гарантируется, что суммарное число заданий во всех тестах не превосходит $10^5$, а также то, что в контрольной была хотя бы одна задача.
Для каждого теста выведите единственное число --- искомое минимальное возможное число плохих студентов.
2 4 3 2 0 1 3 1 5 1
0 3
В первом тесте у Марии Петровны могло быть три трудолюбивых студента, два из которых решили по две задачи, а один --- только одну, и еще один умный студент, который решил самую сложную задачу (но ничего больше решить не успел).
Во втором тесте у Марии Петровны мог быть один умный студент, который решил две последних задачи, четыре трудолюбивых студента, которые решили по две первые задачи и три плохих студента, которые списали первую задачу, каждый у одного из трудолюбивых студентов. В результате из семи решений первой задачи шесть было аннулировано, зачтенным это задание осталось только у трудолюбивого студента, у которого никто не списал.