A. ABCs of Men and Women, Part 2
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Alice, Bob, and Cindy are spending their summer abroad together! Not for a vacation though—they all found internship opportunities at a cluster of schools that are located conveniently close together. Thus, the three of them have decided to room together at a shared apartment for the duration of their stay.

They have been staying at this apartment for $$$n$$$ days so far. During each day, exactly one of Alice or Bob or Cindy is responsible for doing the cooking for that day. They don't particularly care about who handles cooking duty on each day, with whoever was in the mood for it usually being the one to take over. But their parents called and expressed their concern about whether the work was being split fairly.

Specifically, the parents want the following property to hold:

  • There exists a sequence of three consecutive days such that Alice cooked on one day, Bob on another day, and Cindy on the remaining day (not necessarily in that order).
If this condition does not hold, then they should assign cooking duties for the next $$$k$$$ days such that it does hold.

Find the minimum $$$k$$$ number of extra days of cooking duty needed in order for it to be possible for the parents' condition to be satisfied.

Input

The first line of input contains a single integer $$$n$$$.

The second line of input contains a string $$$s$$$ of length $$$n$$$, with each character being A or B or C. The $$$i$$$th letter of $$$s$$$ is A if Alice cooked on the $$$i$$$th day; resp. B for Bob and C for Cindy.

Output

Output a single integer, the minimum number of extra days needed until the parents' condition can be fulfilled.

Scoring

$$$$$$\begin{align*}

&\begin{array}{|l|} \hline \text{Constraints For All Subtasks} \\ \hline \text{The string $s$ contains only }\mathtt{A}\text{ or }\mathtt{B}\text{ or }\mathtt{C}\text{ characters.} \\ 1 \leq n \leq 2 \times 10^5 \\ \hline \end{array}\\

&\begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & \mathbf{20} & n \leq 3 \\ \hline 2 & \mathbf{20} & n \leq 6 \\ \hline 3 & \mathbf{20} & n \leq 500 \\ \hline 4 & \mathbf{20} & \text{There is no }\mathtt{C}\text{ character in $s$.} \\ \hline 5 & \mathbf{20} & \text{No further constraints.} \\ \hline \end{array}\\

\end{align*}$$$$$$

Examples
Input
5
BAABB
Output
2
Input
4
ACBA
Output
0
Note

In the first sample input, we can satisfy the condition after $$$k=2$$$ extra days; for example, we could have Alice cook tomorrow, and then Cindy cook the day after that.

In the second sample input, the condition already holds, so we don't need to use any extra days.