В шеренге плечом к плечу слева направо стоят $$$n$$$ солдат. Голова каждого солдата повернута либо влево, либо вправо, то есть каждый из солдат смотрит либо строго влево, либо строго вправо.
Вам нужно дать некоторым солдатам команду развернуть головы в противоположном направлении, то есть после выполнения этой команды солдат, смотревший влево, должен развернуть голову вправо, а солдат, смотревший вправо, должен развернуть голову влево. После выполнения команды должен существовать солдат, в сторону которого смотрят все остальные солдаты (в какую сторону он смотрит, не имеет значения). Поворачивают голову только те солдаты, которым была отдана команда.
Например, если в шеренге стоят $$$5$$$ солдат, и первые три солдата смотрят вправо, а пятый солдат смотрит влево, то все они смотрят в сторону четвертого солдата.
Определите минимальное количество солдат, которым нужно дать команду развернуть голову, чтобы все солдаты смотрели в сторону какого-то одного солдата.
В первой строке следует целое число $$$n$$$ ($$$2 \le n \le 2\,000$$$) — количество солдат в шеренге.
Во второй строке следует строка $$$s$$$ длины $$$n$$$, состоящая из букв «L» и «R». Если $$$i$$$-й символ строки равен «L», то $$$i$$$-й солдат смотрит влево. Если $$$i$$$-й символ строки равен «R», то $$$i$$$-й солдат смотрит вправо.
Выведите минимальное количество солдат, которым нужно дать команду развернуть голову, чтобы существовал солдат, в сторону которого смотрят все остальные солдаты (в какую сторону он смотрит, не имеет значения).
6 LRRRLR
2
3 LLL
0
10 LLRRLRRRRL
3
В первом примере нужно дать команду повернуть головы, например, первому и шестому солдатам. После этого шеренга будет выглядеть «RRRRLL». Таким образом, все, кроме пятого солдата, будут смотреть на пятого солдата.
Во втором примере все солдаты смотрят влево, то есть второй и третий солдаты смотрят на первого солдата, поэтому отдавать команду повернуть голову не нужно никому.
