Ліхтарі з одним ремонтом#13115

Ліхтарі з одним ремонтом

2 секунди

256 мегабайтів

На колі розташовано $n$ будинків, пронумерованих від $1$ до $n$ . Біля кожного будинку встановлено один ліхтар.

Кожен ліхтар освітлює рівно один із двох сусідніх будинків:

L — будинок ліворуч;
R — будинок праворуч.

Ліхтар не освітлює будинок, біля якого він установлений. Лівим сусідом будинку $i$ є будинок $i - 1$ i-1, а правим — будинок $i + 1$ i+1. Для будинку $1$ лівим сусідом є будинок $n$ , а для будинку $n$ правим сусідом є будинок $1$ .

Ви можете розвернути не більш як один ліхтар, змінивши його напрям із L на R або навпаки.

Знайдіть максимальну кількість будинків, які після цього будуть освітлені рівно одним ліхтарем.

Вхідні дані

Перший рядок містить ціле число $n$ ( $3 \leq n \leq 2 \cdot 1 0^{5}$ 3\le n\le2\cdot10^5) — кількість будинків.

Другий рядок містить рядок $s$ довжини $n$ , що складається із символів L та R. Символ $s_{i}$ s_i визначає напрям ліхтаря біля $i$ -го будинку.

Вихідні дані

Виведіть одне ціле число — максимальну можливу кількість будинків, освітлених рівно одним ліхтарем.

Приклади

Приклад 1

Приклад 2

Приклад 3

Примітка

У першому прикладі розвернемо другий ліхтар. Отримаємо RRRRR, і кожен будинок буде освітлений рівно одним ліхтарем. Відповідь дорівнює $5$ .

У другому прикладі спочатку будинки $1$ та $4$ освітлені двома ліхтарями, а будинки $2$ та $3$ не освітлені. Якщо розвернути перший ліхтар, рівно по одному ліхтарю освітлюватимуть будинки $2$ та $4$ . Отримати більше двох таких будинків неможливо.

У третьому прикладі всі чотири будинки вже освітлені рівно одним ліхтарем, тому можна нічого не змінювати.

Оцінювання

Підзадача $1$ ( $20$ балів): $n \leq 100$ n\le100.
Підзадача $2$ ( $30$ балів): $n \leq 2000$ n\le2000.
Підзадача $3$ ( $50$ балів): без додаткових обмежень.