E. Рассадка на экзамене
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Поликарп сегодня принимает экзамен у студентов. Экзамен пройдет в аудитории, в которой есть один длинный стол, за которым есть $$$n$$$ мест для студентов.

Когда Поликарп зашел в аудиторию, все пришедшие на экзамен студенты уже сели на какие-то места.

Поликарп хочет предотвратить списывание на экзамене, поэтому пересадит некоторых студентов за свободные места так, чтобы выполнялись следующие условия:

  • на самом левом месте за столом должен сидеть студент;
  • на самом правом месте за столом должен сидеть студент;
  • расстояние между всеми парами соседних студентов должно быть одинаковым.

Перед вами стоит задача помочь Поликарпу и определить минимальное количество студентов, которых нужно пересадить так, чтобы выполнялись описанные условия. Считайте, что после пересадки студента место, на котором он сидел, становится свободным.

Входные данные

В первой строке следует целое число $$$n$$$ ($$$2 \le n \le 200\,000$$$) — количество мест за столом.

Во второй строке следует строка $$$s$$$, состоящая из $$$n$$$ символов «F» и «S». Если $$$i$$$-й символ строки равен «F», то $$$i$$$-е слева место за столом свободно. Если $$$i$$$-й символ строки равен «S», то $$$i$$$-е слева место за столом занято ровно одним студентом. Гарантируется, что на экзамен пришли хотя бы два студента.

Выходные данные

Выведите минимальное количество студентов, которых нужно пересадить на свободные места, чтобы экзамен прошел без списывания. Если это невозможно, выведите $$$-1$$$.

Примеры
Входные данные
7
FSSFFFS
Выходные данные
2
Входные данные
11
SFSFSFSFSFS
Выходные данные
0
Входные данные
4
SSFS
Выходные данные
-1
Входные данные
17
FFSSSFFFFFFFSSFFF
Выходные данные
3
Входные данные
6
SSSSSS
Выходные данные
0
Примечание

В первом примере можно, например, пересадить одного студента с места $$$2$$$ на место $$$1$$$ и пересадить другого студента с места $$$3$$$ на место $$$4$$$. Тогда рассадка студентов станет равна «SFFSFFS». Эта рассадка удовлетворяет всем условиям предотвращения списывания, поэтому ответ на этот пример равен $$$2$$$.

Во втором примере никого пересаживать не нужно, так как изначальная рассадка удовлетворяет всем условиям предотвращения списывания, поэтому ответ на этот пример равен $$$0$$$.

В третьем примере невозможно пересадить студентов так, чтобы рассадка удовлетворяла всем условиям предотвращения списывания, поэтому ответ на этот пример равен $$$-1$$$.

В четвертом примере можно, например, пересадить одного студента с места $$$3$$$ на место $$$17$$$, пересадить другого студента с места $$$4$$$ на место $$$1$$$ и пересадить еще одного студента с места $$$14$$$ на место $$$9$$$. Тогда рассадка студентов станет равна «SFFFSFFFSFFFSFFFS». Эта рассадка удовлетворяет всем условиям предотвращения списывания, поэтому ответ на этот пример равен $$$3$$$.

В пятом примере никого пересаживать не нужно, так как изначальная рассадка удовлетворяет всем условиям предотвращения списывания, поэтому ответ на этот пример равен $$$0$$$.