В один ряд стоят n белых и черных коробок. Коробки пронумерованы слева направо от 1-го до n. Просматривая коробки Барыш раздражается, когда видит белую коробку сразу после черной. Поэтому он просит вас поменять местами коробки во всех последовательных парах {черный, белый}.
За один проход Вы сначала определяете все пары коробок {черный, белый}, а после этого меняете местами коробки во всех найденных парах. После одного прохода в ряду все еще могут оставаться последовательные пары {черный,белый}. В этом случае необходимо повторить описанный процесс.
Сколько проходов нужно совершить, чтобы в ряду не осталось ни одной последовательной пары {черный, белый}?
В первой строке дается количество тестов t (1 ≤ t ≤ 100).
В каждом из следующих далее t тестов, в первой строке дается число n (1 ≤ n ≤ 10^4
), а во второй n чисел p[i]
.
p[i]
показывает цвет i-ой коробки: p[i]
= 1 черный цвет, а p[i]
= 0 белый цвет.
Для каждого из тестов в отдельной строке выведите одно число – количество проходов.
Эта задача состоит из 2-х подзадач:
Подзадача | Ограничения | Оценка |
---|---|---|
0 | Пример | 0 баллов |
1 | n ≤ 100 | 15 баллов |
2 | Дополнительных ограничений нет | 85 баллов |