CF883D.Packmen Strike Back

Game field is represented by a line of n square cells. In some cells there are packmen, in some cells there are asterisks and the rest of the cells are empty. Packmen eat asterisks.

Before the game starts you can choose a movement direction, left or right, for each packman. Once the game begins all the packmen simultaneously start moving according their directions. A packman can't change the given direction.

Once a packman enters a cell containing an asterisk, packman immediately eats the asterisk. Once the packman leaves the cell it becomes empty. Each packman moves at speed 1 cell per second. If a packman enters a border cell, the packman stops. 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 assign a direction to each packman so that they eat the maximal number of asterisks. If there are multiple ways to assign directions to eat the maximal number of asterisks, you should choose the way which minimizes the time to do that.

游戏场地由一条包含 $n$ 个方形单元格的直线构成。某些单元格中存在吃豆人（packmen），某些单元格中存在星号（asterisks），其余单元格为空。吃豆人可以吃掉星号。

在游戏开始前，你可以为每个吃豆人选择一个移动方向：向左或向右。游戏一旦开始，所有吃豆人将同时按照各自指定的方向开始移动，且在移动过程中不能改变方向。

当一个吃豆人进入一个含有星号的单元格时，该吃豆人会立即吃掉该星号；当吃豆人离开该单元格后，该单元格变为空。每个吃豆人的移动速度为每秒 1 个单元格。若一个吃豆人进入边界单元格（即最左端或最右端的单元格），则该吃豆人停止移动。吃豆人之间互不干扰；同一单元格中可同时存在任意数量的吃豆人，且它们可以朝任意方向移动。

你的任务是为每个吃豆人分配一个移动方向，使得被吃掉的星号总数最大。如果存在多种分配方案均能达成最大星号数量，则应从中选择使完成该目标所需时间最短的方案。

The first line contains integer number n (2 ≤ n ≤ 1 000 000) — the number of cells in the game field.

The second line contains n characters. If the i-th character is '.', the i-th cell is empty. If the i-th character is '*', the i-th cell contains an asterisk. If the i-th character is 'P', the i-th cell contains a packman.

The field contains at least one asterisk and at least one packman.

第一行包含一个整数 $ n $（$ 2 \leq n \leq 1,000,000 $）——表示游戏场地中的格子数量。

第二行包含 $ n $ 个字符。若第 $ i $ 个字符为 .，则第 $ i $ 个格子为空；若为 *，则第 $ i $ 个格子中有一个星号；若为 P，则第 $ i $ 个格子中有一个吃豆人（Packman）。

场地中至少包含一个星号和一个吃豆人。

Print two integer numbers — the maximal number of asterisks packmen can eat and the minimal time to do it.

输出两个整数——packmen 能吃到的星号（*）的最大数量，以及实现该最大数量所需的最短时间。

In the first example the leftmost packman should move to the right, the rightmost packman should move to the left. All the asterisks will be eaten, the last asterisk will be eaten after 4 seconds.

在第一个例子中，最左边的吃豆人应向右移动，最右边的吃豆人应向左移动。所有星号都将被吃掉，最后一个星号将在 4 秒后被吃掉。