← 返回题目列表

Codeforces · 2195/C

C. 掷骰子序列

中文机器翻译题面 查看原题

考虑以下立方体 $$$D$$$,其中数字 $$$x$$$ 和 $$$7-x$$$ 躺在相对两侧:

由 Nano Banana Pro 生成的图像。

从 $$$1$$$ 到 $$$6$$$ 的整数序列 $$$b$$$ 称为 掷骰子序列 如果满足以下条件:

  • 所有相邻元素对都位于立方体的相邻$$$^{\text{∗}}$$$ 边上。

例如,$$$[1,4,2]$$$ 是掷骰子序列,而 $$$[3,4,6,3]$$$ 不是,因为 $$$3$$$ 和 $$$4$$$ 不在骰子的相邻边上。此外,$$$[2,2,4]$$$ 不是骰子掷序列,因为 $$$2$$$ 和 $$$2$$$ 位于骰子的同一侧(不相邻)。

给定从 $$$1$$$ 到 $$$6$$$ 的 $$$n$$$ 整数序列 $$$a$$$,您可以执行以下操作任意次数(可能为零)。

  • 选择索引 $$$1 \le i \le n$$$ 和整数 $$$1 \le x \le 6$$$。然后,将 $$$a_i$$$ 的值更改为 $$$x$$$。

请确定 最小操作次数 需要使 $$$a$$$ 成为掷骰子序列。

$$$^{\text{*}}$$$立方体的两个面 $$$S$$$ 和 $$$T$$$ 被称为 相邻 如果他们分享 正是 立方体的一条边。 请注意 这个条件也意味着 $$$S \neq T$$$ 。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$)。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le 6$$$)。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$3 \cdot 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]$$$,这是一个掷骰子序列。