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.
## Input
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.
## Output
Print minimum possible time after which Packmen can eat all asterisks.
[samples]
## Note
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.
一个游戏场是一条由 #cf_span[1 × n] 个方格组成的条带。某些格子中有 Packman，某些格子中有星号（asterisk），其余格子为空。
Packman 每个时间单位可以移动到相邻的格子。如果目标格子中有星号，则 Packman 会吃掉它。吃星号不消耗任何时间。
在初始时刻，所有 Packman 同时开始移动。每个 Packman 可以无限次改变移动方向，但不允许超出游戏场的边界。Packman 之间互不干扰；一个格子中可以同时存在任意数量的 Packman，朝任意方向移动。
你的任务是确定 Packman 吃掉所有星号所需的最少时间。
第一行包含一个整数 #cf_span[n]（#cf_span[2 ≤ n ≤ 105]）——游戏场的长度。
第二行包含一个由 #cf_span[n] 个字符组成的字符串，描述游戏场。如果位置 #cf_span[i] 是符号 '_._'，则格子 #cf_span[i] 为空；如果是符号 '_*_'，则格子 #cf_span[i] 中有一个星号；如果是符号 '_P_'，则 Packman 位于该格子。
保证游戏场上至少有一个 Packman 和至少一个星号。
请输出 Packman 吃掉所有星号所需的最少时间。
在第一个例子中，位于位置 #cf_span[4] 的 Packman 向左移动，吃掉位置 #cf_span[1] 的星号，耗时 #cf_span[3] 个时间单位。在同一 #cf_span[3] 个时间单位内，位于位置 #cf_span[6] 的 Packman 吃掉其相邻的两个星号。例如，它可先向左移动，吃掉位置 #cf_span[5] 的星号（耗时 #cf_span[1] 个时间单位），然后从位置 #cf_span[5] 向右移动，吃掉位置 #cf_span[7] 的星号（耗时 #cf_span[2] 个时间单位）。因此，在 #cf_span[3] 个时间单位后，所有星号均被吃掉。
在第二个例子中，位于位置 #cf_span[4] 的 Packman 向左移动，在 #cf_span[2] 个时间单位后吃掉位置 #cf_span[3] 和 #cf_span[2] 的星号；位于位置 #cf_span[5] 和 #cf_span[8] 的 Packman 向右移动，在 #cf_span[2] 个时间单位后分别吃掉位置 #cf_span[7] 和 #cf_span[10] 的星号。因此，#cf_span[2] 个时间单位足以让所有 Packman 吃掉所有星号。
## Input
第一行包含一个整数 #cf_span[n]（#cf_span[2 ≤ n ≤ 105]）——游戏场的长度。第二行包含一个由 #cf_span[n] 个字符组成的字符串，描述游戏场。如果位置 #cf_span[i] 是符号 '_._'，则格子 #cf_span[i] 为空；如果是符号 '_*_'，则格子 #cf_span[i] 中有一个星号；如果是符号 '_P_'，则 Packman 位于该格子。保证游戏场上至少有一个 Packman 和至少一个星号。
## Output
请输出 Packman 吃掉所有星号所需的最少时间。
[samples]
## Note
在第一个例子中，位于位置 #cf_span[4] 的 Packman 向左移动，吃掉位置 #cf_span[1] 的星号，耗时 #cf_span[3] 个时间单位。在同一 #cf_span[3] 个时间单位内，位于位置 #cf_span[6] 的 Packman 吃掉其相邻的两个星号。例如，它可先向左移动，吃掉位置 #cf_span[5] 的星号（耗时 #cf_span[1] 个时间单位），然后从位置 #cf_span[5] 向右移动，吃掉位置 #cf_span[7] 的星号（耗时 #cf_span[2] 个时间单位）。因此，在 #cf_span[3] 个时间单位后，所有星号均被吃掉。
在第二个例子中，位于位置 #cf_span[4] 的 Packman 向左移动，在 #cf_span[2] 个时间单位后吃掉位置 #cf_span[3] 和 #cf_span[2] 的星号；位于位置 #cf_span[5] 和 #cf_span[8] 的 Packman 向右移动，在 #cf_span[2] 个时间单位后分别吃掉位置 #cf_span[7] 和 #cf_span[10] 的星号。因此，#cf_span[2] 个时间单位足以让所有 Packman 吃掉所有星号。
**Definitions**
Let $ n \in \mathbb{Z} $, $ 2 \leq n \leq 10^5 $, be the length of the field.
Let $ F \in \{ \text{'.', '*', 'P'} \}^n $ be the field configuration, where:
- $ F[i] = \text{'P'} $ indicates a Packman at position $ i $ (1-indexed),
- $ F[i] = \text{'*'} $ indicates an asterisk at position $ i $,
- $ F[i] = \text{'.'} $ indicates an empty cell.
Let $ P = \{ p_1, p_2, \dots, p_m \} \subseteq \{1, \dots, n\} $ be the set of Packman positions, with $ m \geq 1 $.
Let $ A = \{ a_1, a_2, \dots, a_k \} \subseteq \{1, \dots, n\} $ be the set of asterisk positions, with $ k \geq 1 $.
**Constraints**
1. Each Packman moves at speed 1 cell per time unit.
2. Packmen may change direction arbitrarily and without cost.
3. Packmen may occupy the same cell simultaneously.
4. An asterisk is eaten immediately upon a Packman’s arrival to its cell.
5. All Packmen start moving at time $ t = 0 $.
**Objective**
Find the minimum time $ T \in \mathbb{R}_{\geq 0} $ such that there exists a strategy for each Packman $ p_j \in P $ to move within time $ T $ and collectively cover all asterisk positions $ A $, i.e., for every $ a_i \in A $, there exists some $ p_j \in P $ and a path from $ p_j $ to $ a_i $ of length $ \leq T $.
Equivalently:
$$
T = \min \left\{ \max_{a \in A} \min_{p \in P} d(p, a) \text{ under partitioning of } A \text{ among Packmen} \right\}
$$
where $ d(p, a) = |p - a| $, and each asterisk is assigned to exactly one Packman, who must traverse the distance to it, possibly visiting multiple asterisks along a path.
**Note**: The optimal strategy allows each Packman to cover a contiguous interval of asterisks (possibly after backtracking), and the total time is determined by the Packman with the maximum travel time.