吃豆人 (Pac-Man) 在 1980 年代风靡全球，被认为是最经典的街机游戏之一。游戏的目的就是控制游戏的主角小精灵吃掉藏在迷宫内所有的豆子，并且不能被鬼魂抓到。

我们考虑一个简化版的吃豆人，游戏区域是一个 1 × n 的方格图。在一些格子里有吃豆人（用字符‘C’表示），一些格子里有豆子（用字符‘*’表示)，剩下的格子是空的（用字符‘.’表示)。

吃豆人可以花费一个单位时间移动到和它相邻的格子，如果那个格子里有豆子那么吃豆人可以吃掉它，我们认为吃豆子不花费时间。

在一开始，所有的吃豆人同时开始移动。每个吃豆人的行进方向都可以切换无限多次，但是它不能走出游戏区域。吃豆人之间互不影响，也就是说在同一时刻一个格子中可能有多个行进方向互不相同的吃豆人。

小 Z 想知道如何决定每个吃豆人的行进轨迹，可以使得所有豆子都被吃完所花费的时间最短。

输入包含两行，第一行包含一个整数 n，表示游戏区域的大小。

第二行包含 n 个字符，每个字符是 {'C', '*', '.'} 中的一个。

仅一行，即花费的最短时间。

样例解释 1

第一个吃豆人先向右走一步，再向左走两步可以吃掉前两个豆子；第二个吃豆人向右走三步可以吃掉第三个豆子。

总共需要 3 个单位时间。

数据规模与约定

对于 10% 的数据，1 ≤ n ≤ 10；

对于 40% 的数据，1 ≤ n ≤ 1000；

另外 30% 的数据，吃豆人的数量不超过 3；

对于 100% 的数据，1 ≤ n ≤ 100000。