Organizing Medicine

At Sena's request, you must organize $N$ medicines arranged in a row on a shelf. You want the medicines on the shelf to be of the same types as much as possible. Currently, the label on the $i$-th medicine bears an uppercase letter $m_i$, representing its type.

To organize the medicines, you may perform each of the following three operations as many times as you wish.

• Replace the $i$-th medicine with a type different from both the current $m_{i-1}$ and $m_{i+1}$. $(1 \lt i \lt N)$
• Replace the $1$-st medicine with a type different from the current $m_{2}$.
• Replace the $N$-th medicine with a type different from the current $m_{N-1}$.

If an operation replaces some $m_x$, subsequent operations use the updated value of $m_x$. $(1 \le x \le N)$

You want to minimize the number of distinct types of medicine after organizing them. Find this minimum number and a final arrangement achieving it.

If there are multiple possible final arrangements, print any of them.

Time limit

1000 ms

Memory limit

1024 MB

Checker

CUSTOM