Packmen Strike Back

题意翻译

有一个长度为 $n$ 的字符串，字符串中每个字符为`.`，`P`，`*`三种情况之一。当字符为 `.` 时表示为空地，当为 `P` 时表示为吃豆人，当为 `*` 时表示为豆子。 在一开始，你可以给吃豆人规定一个方向（向左或者向右），然后吃豆人会沿着你规定的方向以 $1$ 格每秒的速度走到边界，同时吃完这个方向上的所有豆子。吃豆子不消耗时间，同时一个豆子被吃一次之后就会消失。每个吃豆人的路径互不干涉，即相遇后不会改变方向，同时一个格子上可以有任意多个吃豆人。 你希望这些吃豆人吃到的豆子数目最多，与此同时保证所用时间最短。 $2 \leq n \leq 10^6$

题目描述

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.

输入输出格式

输入格式

The first line contains integer number $ n $ ( $ 2<=n<=1000000 $ ) — 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.

输出格式

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

输入输出样例

输入样例 #1

6
*.P*P*

输出样例 #1

3 4

输入样例 #2

8
*...P..*

输出样例 #2

1 3

说明

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.