题目描述

一条校准带由 0、1、2 三种数字组成。设长度为 $n$ 的校准带为 $t$，位置从 $1$ 开始编号。如果存在 $p\in\{0,1,2\}$，使得对每个 $1\le i\le n$ 都有

那么称 $t$ 处于合法校准状态。这里取模后的结果为 $0,1,2$ 之一。

例如，0120120、1201201 和 2012012 分别对应 $p=0,1,2$，都是长度为 $7$ 的合法校准状态。

现在给定一条长度为 $n$ 的校准带 $s$。你可以不进行操作，也可以进行至多一次如下操作：

• 选择一个非空连续区间 $[l,r]$，其中 $1\le l\le r\le n$；
• 选择 $k\in\{1,2\}$；
• 对区间中的所有位置同时操作，把每个数字 $x$ 变为 $(x+k)\bmod 3$。

不进行操作的代价为 $0$。进行操作的代价为所选区间的长度 $r-l+1$。

求使校准带变为任意一个合法校准状态的最小代价。如果无论如何都不能做到，输出 -1。

输入格式

从文件 phaseband.in 中读取数据。

输入共两行。

第一行包含一个整数 $n$。

第二行包含一个长度恰为 $n$ 的字符串 $s$，其中每个字符均为 0、1 或 2。

输出格式

输出到文件 phaseband.out 中。

输出一个整数，表示最小代价；如果无法变为合法校准状态，输出 -1。

答案是唯一的整数。忽略 ASCII 空白后，选手输出必须只含一个与标准答案相同的整数 token，不能含有其他非空白内容。

样例输入 #1

6
120120

样例输出 #1

0

样例输入 #2

7
0112020

样例输出 #2

3

样例输入 #3

3
000

样例输出 #3

-1

样例输入 #4

6
122012

样例输出 #4

2

样例解释

样例 #1：

原字符串已经是 $p=1$ 的合法校准状态，所以不操作即可，代价为 $0$。

如果对整个区间 $[1,6]$ 取 $k=1$，会得到 201201；取 $k=2$，会得到 012012。这两个结果也合法，但代价均为 $6$，不如不操作。

样例 #2：

选择区间 $[3,5]$ 和 $k=1$ 后，字符串变为 0120120，代价为 $3$。不存在代价更小的可行方案。

样例 #3：

长度为 $3$ 的合法校准状态只有 012、120 和 201。一次操作只能把一个连续区间内的所有 0 变成同一个非零数字，无法得到其中任何一个状态。

样例 #4：

选择 $[1,2]$ 和 $k=2$ 可以得到 012012，代价为 $2$。此外，选择 $[3,6]$ 和 $k=1$ 可以得到 120120，代价为 $4$。因此答案为 $2$。

数据规模与约定

对于所有数据，$1\le n\le 200000$。

本题采用子任务捆绑计分。只有通过某个子任务内的所有测试点，才能获得该子任务的分数。各子任务独立计分。

下发文件

包含本题额外3组大数据的输入与输出文件。

下载三组测试数据，非真实测试数据