Задана горизонтальная клетчатая полоса из \(n\) клеток. В \(i\)-й клетке находится заряд краски величины \(a_i\). Этот заряд можно:
Обратите внимание, что заряд можно использовать не более одного раза (то есть его нельзя использовать одновременно и влево и вправо). Допустимо, что клетка окажется покрашена более одного раза.
Какое минимальное количество раз заряд необходимо использовать, чтобы покрасить все клетки полосы?
В первой строке входных данных содержится целое число \(t\) (\(1 \le t \le 100\)) — количество наборов входных данных в тесте. Далее следуют описания \(t\) наборов входных данных.
Каждый набор входных данных задаётся двумя строками. Первая из них содержит целое число \(n\) (\(1 \le n \le 100\)) — количество клеток в полосе. Вторая строка содержит \(n\) положительных целых чисел \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le n\)), где \(a_i\) — величина заряда краски в \(i\)-й слева клетке полосы.
Гарантируется, что сумма значений \(n\) в тесте не превосходит \(1000\).
Для каждого набора входных данных выведите минимальное количество раз, сколько необходимо использовать заряды, чтобы покрасить все клетки полосы.
В третьем наборе входных данных примера достаточно использовать заряд из \(1\)-й клетки вправо, тогда он покроет обе клетки \(1\) и \(2\).
В девятом наборе входных данных примера нужно:
В одиннадцатом наборе входных данных примера нужно:
13 1 1 2 1 1 2 2 1 2 1 2 2 2 2 3 1 1 1 3 3 1 2 3 1 3 1 7 1 2 3 1 2 4 2 7 2 1 1 1 2 3 1 10 2 2 5 1 6 1 8 2 8 2 6 2 1 2 1 1 2 6 1 1 4 1 3 2
1 2 1 1 1 3 1 2 3 4 2 3 3
4000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач