P15459 [MX-X25-T3] "FeOI-5" qjyxfgms

"qjyxfgms" is very likely an abbreviation made from the initial letters of Chinese pinyin. A common interpretation is: **"请假一下发给秘书"** ("qing jia yi xia fa gei mi shu", meaning "Please ask for leave and send it to the secretary".).

You are given a 01 sequence $a$ of length $n$. You can perform several operations on this sequence. In each operation, you may choose a position $i(1\le i\le n-2)$, and assign $a_i,a_{i+1},a_{i+2}$ to $mex(\{a_i,a_{i+1},a_{i+2}\})$. You need to find the minimum number of operations to make all positions become $0$. Here, $mex(S)$ denotes the smallest natural number that does not appear in the set $S$.

**This problem contains multiple test cases.** The first line contains a positive integer $T$, denoting the number of test cases. For each test case: - The first line contains a positive integer $n$. - The second line contains $n$ integers $a_1, \ldots, a_n$, where $a_i\in\{0,1\}$.

For each test case, output one line with a non-negative integer, representing the answer.

**[Sample Explanation #1]** For the first test case: * In the $1$st operation, choose position $3$. Since $mex(\{a_3,a_4,a_5\})=mex(\{0,1,0\})=2$, the sequence becomes $[1,1,2,2,2,1]$. * In the $2$nd operation, choose position $1$. Since $mex(\{a_1,a_2,a_3\})=mex(\{1,1,2\})=0$, the sequence becomes $[0,0,0,2,2,1]$. * In the $3$rd operation, choose position $4$. Since $mex(\{a_4,a_5,a_6\})=mex(\{2,2,1\})=0$, the sequence becomes $[0,0,0,0,0,0]$. In total, $3$ operations are used to make all positions become $0$. It can be proven that no solution with fewer operations exists. **[Constraints]** **This problem uses bundled tests.** For all test cases, it is guaranteed that: - $1\le T\le 10^6$; - $3\le n,\sum n\le 10^6$; - $a_i\in\{0,1\}$. ::cute-table{tuack} | Subtask ID | $n\le$ | Special Property | Score | | :--------: | :----: | :--------------: | :---: | | $1$ | $15$ | None | $21$ | | $2$ | $10^2$ | A | $18$ | | $3$ | $10^3$ | B | $24$ | | $4$ | $10^6$ | C | $17$ | | $5$ | $10^6$ | None | $20$ | Special Property A: $\sum n^3\le 3\times 10^7$. Special Property B: $\sum n^2\le 3\times 10^7$. Special Property C: it is guaranteed that the number of positions $i$ satisfying $a_i=0$ does not exceed $15$. Translated by ChatGPT 5