E. Пакманы
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Игровое поле представляет собой клетчатую полоску 1 × n. В некоторых клетках находятся пакманы, в некоторых клетках — звёздочки, остальные клетки пусты.

Пакман может перемещаться в соседнюю клетку за 1 единицу времени. Если в клетке находится звёздочка, то пакман в момент перемещения в эту клетку съедает звёздочку. Пакман съедает звездочку мгновенно.

В начальный момент времени все пакманы начинают двигаться. Каждый из пакманов может неограниченное количество раз менять направление движения, но не должен выходить за пределы игрового поля. Пакманы не создают помех движению других пакманов; в одной клетке может находиться произвольное количество пакманов, движущихся в произвольных направлениях.

Ваша задача — определить минимально возможное время, за которое пакманы смогут съесть все звёздочки.

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

В первой строке содержится целое число n (2 ≤ n ≤ 105) — длина игрового поля.

Во второй строке содержится описание игрового поля, состоящее из n символов. Если на позиции i записан символ '.', то клетка i — пуста. Если на позиции i записан символ '*', то в клетке i находится звёздочка. Если же на позиции i записан символ 'P', в клетке i находится пакман.

Гарантируется, что на игровом поле есть хотя бы один пакман и хотя бы одна звёздочка.

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

Выведите минимальное время, за которое пакманы смогут съесть все звёздочки.

Примеры
Входные данные
7
*..P*P*
Выходные данные
3
Входные данные
10
.**PP.*P.*
Выходные данные
2
Примечание

В первом примере пакман, находящийся на позиции 4, отправится влево и съест звёздочку на позиции 1. На это у него уйдёт 3 единицы времени. За эти же 3 единицы времени пакман, находящийся на позиции 6, успеет съесть обе соседние с ним звёздочки. Например, сначала он может пойти влево и съесть звёздочку на позиции 5, затратив 1 единицу времени, а потом из позиции 5 пойти вправо и съесть звёздочку на позиции 7, затратив на это ещё 2 единицы времени. Таким образом, за 3 единицы времени пакманы съедят все звёздочки на игровом поле.

Во втором примере пакман, находящийся на позиции 4, пойдёт влево и спустя 2 единицы времени уже съест звёздочки на позициях 3 и 2. Пакманы же, находящиеся на позициях 5 и 8, будут двигаться вправо и в течение 2 единиц времени съедят звёздочки на позициях 7 и 10, соответственно. Таким образом, пакманам достаточно 2 единиц времени для поедания всех звёздочек на игровом поле.