CF847E.Packmen

A game field is a strip of 1 × n square cells. In some cells there are Packmen, in some cells — asterisks, other cells are empty.

Packman can move to neighboring cell in 1 time unit. If there is an asterisk in the target cell then Packman eats it. Packman doesn't spend any time to eat an asterisk.

In the initial moment of time all Packmen begin to move. Each Packman can change direction of its move unlimited number of times, but it is not allowed to go beyond the boundaries of the game field. Packmen do not interfere with the movement of other packmen; in one cell there can be any number of packmen moving in any directions.

Your task is to determine minimum possible time after which Packmen can eat all the asterisks.

游戏场地是一条 $1 \times n$ 的方格单元带。某些单元格中放置有“吃豆人”（Packmen），某些单元格中放置有星号（asterisks），其余单元格为空。

吃豆人每单位时间可向相邻单元格移动一格。若目标单元格中存在星号，则吃豆人将其吃掉。吃豆人吃掉星号不消耗额外时间。

在初始时刻，所有吃豆人同时开始移动。每个吃豆人可无限次改变移动方向，但不允许移出游戏场地边界。吃豆人之间互不干扰；同一单元格中可同时存在任意数量的吃豆人，且它们可朝任意方向移动。

你的任务是求出所有星号均被吃掉所需的最短时间。

The first line contains a single integer n (2 ≤ n ≤ 105) — the length of the game field.

The second line contains the description of the game field consisting of n symbols. If there is symbol '.' in position i — the cell i is empty. If there is symbol '*' in position i — in the cell i contains an asterisk. If there is symbol 'P' in position i — Packman is in the cell i.

It is guaranteed that on the game field there is at least one Packman and at least one asterisk.

第一行包含一个整数 $n$（$2 \leq n \leq 10^5$）—— 表示游戏场地的长度。

第二行包含一个由 $n$ 个字符组成的字符串，用于描述游戏场地。若位置 $i$ 上的字符为 .，则表示第 $i$ 个格子为空；若为 *，则表示第 $i$ 个格子中有一个星号；若为 P，则表示 Packman 位于第 $i$ 个格子中。

保证游戏场地上至少有一个 Packman 和至少一个星号。

Print minimum possible time after which Packmen can eat all asterisks.

输出所有“小人”吃完所有星号（*）所需的最短时间。

In the first example Packman in position 4 will move to the left and will eat asterisk in position 1. He will spend 3 time units on it. During the same 3 time units Packman in position 6 will eat both of neighboring with it asterisks. For example, it can move to the left and eat asterisk in position 5 (in 1 time unit) and then move from the position 5 to the right and eat asterisk in the position 7 (in 2 time units). So in 3 time units Packmen will eat all asterisks on the game field.

In the second example Packman in the position 4 will move to the left and after 2 time units will eat asterisks in positions 3 and 2. Packmen in positions 5 and 8 will move to the right and in 2 time units will eat asterisks in positions 7 and 10, respectively. So 2 time units is enough for Packmen to eat all asterisks on the game field.

在第一个例子中，位于位置 4 的吃豆人将向左移动，并吃掉位置 1 处的星号，耗时 3 个时间单位。在同一段 3 个时间单位内，位于位置 6 的吃豆人将吃掉其左右两侧相邻的两个星号。例如，它可先向左移动，在 1 个时间单位内吃掉位置 5 处的星号，再从位置 5 向右移动，在 2 个时间单位内吃掉位置 7 处的星号。因此，吃豆人们仅需 3 个时间单位即可吃掉游戏区域中的所有星号。

在第二个例子中，位于位置 4 的吃豆人将向左移动，经过 2 个时间单位后吃掉位置 3 和位置 2 处的星号；位于位置 5 和位置 8 的吃豆人则向右移动，分别在 2 个时间单位内吃掉位置 7 和位置 10 处的星号。因此，仅需 2 个时间单位，吃豆人们即可吃掉游戏区域中的所有星号。