Коробки#10454

Коробки

1 секунда

256 мегабайтів

Середня

У ряду розташовано $n$ коробок, кожна з яких пофарбована або в білий, або в чорний колір. Коробки пронумеровані зліва направо від $1$ до $n$ . Бариш дратується, коли бачить білу коробку одразу після чорної. Тому він просить вас поміняти місцями коробки у кожній послідовній парі ${чорна, біла}$ \{\text{чорна}, \text{біла}\}.

За один прохід спочатку знаходьте всі послідовні пари коробок ${чорна, біла}$ \{\text{чорна}, \text{біла}\}, а потім міняйте місцями коробки у кожній знайденій парі. Після одного проходу в ряду все ще можуть залишатися послідовні пари ${чорна, біла}$ \{\text{чорна}, \text{біла}\}. У такому випадку потрібно повторювати описаний процес.

Скільки проходів потрібно виконати, щоб у ряду не залишилось жодної послідовної пари ${чорна, біла}$ \{\text{чорна}, \text{біла}\}?

Вхідні дані

Перший рядок містить ціле число $t$ ( $1 \leq t \leq 100$ 1 \le t \le 100) — кількість тестових випадків.

У кожному тесті у першому рядку дане ціле число $n$ ( $1 \leq n \leq 1 0^{4}$ 1 \le n \le 10^4) — кількість коробок. У другому рядку розміщено $n$ чисел $p_{1}, p_{2}, \dots, p_{n}$ p_1, p_2, \ldots, p_n.

Кожне $p_{i}$ p_i вказує на колір $i$ -ї коробки: $p_{i} = 1$ p_i = 1 означає чорний колір, $p_{i} = 0$ p_i = 0 — білий колір.

Вихідні дані

Для кожного тесту виведіть у окремому рядку одне число — кількість потрібних проходів.

Приклади

Приклад 1

Примітка

Обмеження

$1 \leq t \leq 100$ 1 \le t \le 100
$1 \leq n \leq 1 0^{4}$ 1 \le n \le 10^4
$p_{i} \in {0, 1}$ p_i \in \{0, 1\}

Оцінювання

Це завдання складається з $2$ підзадач:

Підзадача	Обмеження	Бали
0	Приклад	0
1	$n \leq 100$ n \le 100	15
2	Додаткових обмежень нема	85