Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
D. Packmen Strike Back

time limit per test

3 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputGame 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.

Input

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.

Output

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

Examples

Input

6

*.P*P*

Output

3 4

Input

8

*...P..*

Output

1 3

Note

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.

Codeforces (c) Copyright 2010-2022 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/02/2022 07:05:31 (g2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|