RGB рядок#12320

RGB рядок

1 секунда

256 мегабайтів

Середня

Вам дано рядок $s$ довжини $n$ , що складається лише з символів R, G, B.

Рядок вважається циклічним: після символа $s_{n}$ s_n йде $s_{1}$ s_1, тобто індекси рахуються по модулю $n$ (наприклад, $s_{n + 1} = s_{1}$ s_{n+1}=s_1, $s_{n + 2} = s_{2}$ s_{n+2}=s_2).

Для кожної позиції $i$ розглянемо трійку послідовних символів $(s_{i}, s_{i + 1}, s_{i + 2}),$ (s_i,\; s_{i+1},\; s_{i+2}), де всі індекси беруться по модулю $n$ .

Назвемо трійку гарною, якщо всі три символи в ній попарно різні (тобто це R, G, B у будь-якому порядку).

За одну операцію ви можете вибрати будь-яку позицію $i$ та змінити $s_{i}$ s_i на будь-який з трьох символів R, G, B. Вартість операції дорівнює $1$ .

Знайдіть мінімальну кількість операцій, необхідних для того, щоб для кожного $i = 1, 2, \dots, n$ i=1,2,\dots,n трійка $(s_{i}, s_{i + 1}, s_{i + 2})$ (s_i, s_{i+1}, s_{i+2}) була гарною.

Вхідні дані

В першому рядку задано число $n$ $(1 \leq n \leq 1 0^{6})$ (1 \le n \le 10^6) — довжина рядка $s$ .

В другому рядку задано рядок $s$ який складається з символів $R$ , $G$ , $B$ .

Вихідні дані

Потрібно вивести одне число — мінімальну кількість операцій, необхідну для того, щоб усі трійки $(s_{i}, s_{i + 1}, s_{i + 2})$ (s_i, s_{i+1}, s_{i+2}) для $i = 1, 2, \dots, n$ i=1,2,\dots,n стали гарними.

Якщо це неможливо, виведіть $- 1$ .

Приклади

Приклад 1

Приклад 2

Примітка

Для другого тестового випадку відповідь $3$ досягається при перетворенні рядка $R R GB GR$ в рядок $B GR B GR$ .

Оцінювання

Підзадача $1$ ( $15$ балів) : $(n \leq 15)$ (n \le 15)
Підзадача $2$ ( $25$ балів) : (Рядок складається лише з $2$ різних символів)
Підзадача $3$ ( $40$ балів) : $(n \leq 5000)$ (n \le 5000)
Підзадача $4$ ( $70$ балів) : Без додаткових обмежень