题目描述

有一个长度为 $n$ 的信号串，只包含字母 A、B、C、D，并且每种字母都至少出现一次。

每次操作，你可以选择串中任意两个不同的位置，交换这两个位置的字母。请用尽量少的操作，使信号串中出现连续子串 ABCD。除此之外，其他位置的字母不作要求。

求最少需要的操作次数。

输入格式

第一行包含一个整数 $n$，表示信号串的长度。

第二行包含一个长度为 $n$ 的字符串，表示初始的信号串。

输出格式

输出一行一个整数，表示最少需要的交换次数。

样例输入 1

5
ABDAC

样例输出 1

2

样例 1 解释

先交换第 $3$、$5$ 个位置，再交换第 $4$、$5$ 个位置，得到 ABCDA，共进行 $2$ 次操作。只交换一次无法得到所需子串。

样例输入 2

4
BDAC

样例输出 2

3

样例 2 解释

依次交换位置 $(1,3)$、$(2,4)$、$(2,3)$，信号串依次变为 ADBC、ACBD、ABCD。最少需要 $3$ 次操作。

数据范围与子任务

对于所有测试数据，保证$4\le n\le2\times10^5$。字符串只含 A、B、C、D，且每种字母至少出现一次。

每个子任务内的正式测试全部通过，才获得该子任务的分数。