Екзамен
Марія Петрівна працює викладачем в університеті. В середині семестру вона дала своїм студентам контрольну роботу, у якій було n завдань, упорядкованих за зростанням складності.
Марія Петрівна знає, що кожен з її студентів відноситься до однієї з трьох категорій:
Трудолюбивий студент розв'язує на контрольній задачі у порядку збільшення складності, починаючи з самої легкої, і не пропускаючи жодної задачі, доки не закінчиться час контрольної.
Розумний студент розв'язує на контрольній задачі у порядку зменшення складності, починаючи з самої складної, і не пропускаючи жодної задачі, також доки не завершиться час контрольної.
Поганий студент списує рівно одну задачу у якогось трудолюбивого чи розумного студента. При цьому, два поганих студенти не можуть списати одну і ту же задачу у однієї і тієї ж людини.
Трудолюбиві та розумні студенти завжди правильно розв'язують усі задачі, які встигають.
Марія Петрівна дуже не любить студентів, які списують. Тому, якщо вона взнає, що хтось у когось списав, то обом студентам вона цю задачу не зараховує. За результатами контрольної Марія Петрівна внесла у відомість зараховані задачі для кожного студента і для кожної задачі порахувала, скільком студентам вона її зарахувала.
Оскільки наближаються екзамени, Марія Петрівна вирішила оцінити число поганих студентів у групі, щоб спланувати час на перездачі. На жаль, вона втратила відомість з зарахованими задачами і зберігла лише листочок, у якому записано для кожної задачі, якому числу студентів ця задача зарахована.
Марія Петрівна цікавиться, яке мінімальне число поганих студентів може бути у групі. Допоможіть їй це вияснити.
Вхідні дані
Вхідний файл містить декілька тестів. У першому рядку вхідного файла міститься ціле число T — кількість тестів. Далі йдуть описи тестів.
Опис кожного тесту складається з двох рядків. У першому рядку опису задано ціле число n — кількість завдань у контрольній роботі. Далі для кожного завдання, у порядку зростання складності, вказано число a_i — кількість студентів, яким зарахована відповідна задача (0 ≤ a_i ≤ 10^9).
Гарантується, що сумарне число завдань у всіх тестах не перевищуєт 10^5, а також те, що в контрольній була хоча б одна задача.
Вихідні дані
Для кожного тесту виведіть єдине число — шукане мінімально можливе число поганих студентів.
Пояснення до прикладів
В першому тесті у Марії Петрівни могло бути три трудолюбивих студенти, два з яких розв'зали по дві задачі, а один — лише одну, і ще один розумний студент, який розв'язав саму складну задачу (але нічего більше розв'зати не встиг).
У другому тесті у Марії Петрівни міг бути один розумний студент, який зробив дві останніх задачі, чотири трудолюбивих студенти, які розв'зали по дві перші задачі і три поганих студенти, які списали першу задачу, кожен у одного з трудолюбивих студентів. У результаті з семи розв'зків першої задачі шість було анульовано, зарахованим це завдання залишилось лише у трудолюбивого студента, у якого ніхто не списав.