Qutular#10454

Qutular

1 saniyə

256 meqabayt

Orta

Bir sırada $n$ ədəd ağ və qara qutu düzülüb. Qutular soldan-sağa $1$ -dən $n$ -ə qədər nömrələnmişdir. Barış, qara qutudan dərhal sonra gələn ağ qutunu görəndə qıcıqlanır. Buna görə də o, sizdən bütün ardıcıl ${qara, a g ˘}$ \{\text{qara}, \text{ağ}\} cütlərində qutuların yerlərini dəyişməyi xahiş edir.

Bir mərhələdə əvvəlcə bütün ardıcıl ${qara, a g ˘}$ \{\text{qara}, \text{ağ}\} qutu cütlərini müəyyən edirsiniz və sonra hər bir tapılmış cütdə qutuların yerlərini dəyişirsiniz. Bir mərhələdən sonra, sırada hələ də ardıcıl ${qara, a g ˘}$ \{\text{qara}, \text{ağ}\} cütləri qala bilər. Belə hal olduqda, prosesi təkrar etməlisiniz.

Neçə mərhələ tələb olunur ki, ardıcıl ${qara, a g ˘}$ \{\text{qara}, \text{ağ}\} qutu cütü qalmasın?

Giriş

Birinci sətirdə tam ədəd $t$ ( $1 \leq t \leq 100$ 1 \le t \le 100) — testlərin sayı verilir.

Hər test üçün birinci sətirdə tam ədəd $n$ ( $1 \leq n \leq 1 0^{4}$ 1 \le n \le 10^4) — qutuların sayı, ikinci sətirdə $n$ ədəd $p_{1}, p_{2}, \dots, p_{n}$ p_1, p_2, \ldots, p_n verilir.

$p_{i}$ p_i $i$ -ci qutunun rəngini göstərir: $p_{i} = 1$ p_i = 1 — qara rəng, $p_{i} = 0$ p_i = 0 — ağ rəng.

Çıxış

Hər test üçün cavabı yeni sətrdə bir tam ədəd kimi çıxışa yazın — tələb olunan mərhələlərin sayı.

Nümunələr

Nümunə 1

Qeyd

Məhdudiyyətlər

$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\}

Bal hesablama

Bu məsələ $2$ alt tapşırıqdan ibarətdir:

Alt tapşırıq	Məhdudiyyətlər	Ballar
0	Nümunə	0
1	$n \leq 100$ n \le 100	15
2	Əlavə məhdudiyyət yoxdur	85