题目描述

考虑下述立方体 $D$，其中数字 $x$ 与 $7-x$ 分别位于相对的面上：

一个长度为 $n$，元素均为 $1$ 到 $6$ 之间整数的序列 $b$，如果满足以下条件，则称为一个“骰子掷法序列”：

• 任意相邻两个元素所在的面在立方体中必须是相邻的（即“相邻面”$^\ast$）。

例如，$[1, 4, 2]$ 是一个骰子掷法序列，但 $[3, 4, 6, 3]$ 并不是，因为 $3$ 和 $4$ 不在相邻的骰子面上。另外，$[2, 2, 4]$ 也不是骰子掷法序列，因为 $2$ 和 $2$ 属于同一个面，并不相邻。

给定一个长度为 $n$ 的序列 $a$，其元素均在 $1$ 到 $6$ 之间。你可以对其进行如下操作任意次（包括零次）：

• 选择一个下标 $1 \le i \le n$ 和一个数字 $1 \le x \le 6$，然后将 $a_i$ 改为 $x$。

请你求出，至少需要多少次操作才能将 $a$ 变为一个骰子掷法序列。

$^\ast$ 立方体的两个面 $S$ 和 $T$，如果正好共享一条棱，则称它们是“相邻面”。注意，这也意味着 $S\neq T$。

输入格式

每组数据包含多个测试用例。第一行为测试用例的数量 $t$（$1 \le t \le 10^4$）。接下来依次给出每个测试用例：

每组测试用例的第一行为一个整数 $n$（$1 \le n \le 3 \times 10^5$）。

第二行为 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 6$）。

保证所有测试用例中 $n$ 的总和不超过 $3 \times 10^5$。

输出格式

对于每个测试用例，输出将 $a$ 变为骰子掷法序列所需的最少操作次数。

样例

3
3
1 4 2
4
3 4 6 3
10
6 1 4 3 1 3 2 5 4 4

0
1
4

样例说明

对于第一个测试用例，序列 $a = [1, 4, 2]$ 已经是骰子掷法序列，所以答案是 $0$ 次。

对于第二个测试用例，序列 $a = [3, 4, 6, 3]$。

只需修改一个元素，即可得到 $[3,\color{red}{5},6,3]$，这是一个骰子掷法序列。

对于第三个测试用例，序列 $a = [6,1,4,3,1,3,2,5,4,4]$。

只需修改 $4$ 个元素，就可以得到 $[\color{red}{5},1,4,\color{red}{2},1,3,2,\color{red}{1},\color{red}{5},4]$，这是一个骰子掷法序列。

由 ChatGPT 5 翻译

来源

Codeforces 2195C，英文题名 Dice Roll Sequence。