Codeforces Round 807 (Div. 2) |
---|
Закончено |
Марк убирает ряд из $$$n$$$ комнат, $$$i$$$-я комната имеет неотрицательный уровень запыленности $$$a_i$$$. У него есть волшебная чистящая машина, которая может выполнять следующую трехэтапную операцию:
Цель Марка — сделать $$$a_1 = a_2 = \ldots = a_{n-1} = 0$$$, тогда он сможет перейти к уборке комнаты $$$n$$$. Требуется определить минимальное количество операций, необходимых для достижения его цели.
Первая строка входных данных содержит одно целое число $$$t$$$ ($$$1\leq t\leq 10^4$$$) — количество наборов входных данных в тесте.
Первая строка каждого набора содержит одно целое число $$$n$$$ ($$$2\leq n\leq 2\cdot 10^5$$$) — количество комнат.
Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$0\leq a_i\leq 10^9$$$) — уровень пыли в каждой из комнат.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2\cdot 10^5$$$.
Для каждого набора входных данных выведите строку, содержащую одно целое число — минимальное количество операций. Можно доказать, что существует последовательность операций, удовлетворяющая требованию задачи.
432 0 050 2 0 2 062 0 3 0 4 640 0 0 10
3 5 11 0
В первом наборе входных данных примера возможна следующая последовательность операций:
После этого $$$a_1=a_2=0$$$.
Во втором наборе входных данных примера возможна следующая последовательность операций:
После пятой операции массив удовлетворяет требованиям задачи.
Название |
---|