马里奥最近发现物理引擎进行了一次更新：现在当他处于小马里奥（Small Mario）形态时，他可以跑得更快。这给速通玩家们带来了不小的困扰。

为了简化问题，我们将关卡视为一个 $1 \times N$ 的网格。马里奥从第 $1$ 个网格出发，当他到达第 $N$ 个网格时即通关。

每个网格上可能有一个问号方块（用 ? 表示）、一个电锯（用 S 表示），或者什么都没有（用 . 表示）。保证第一个网格和第 $N$ 个网格都是空的。

马里奥可以处于以下三种形态之一：小马里奥（Small Mario）、超级马里奥（Super Mario）或火焰马里奥（Fire Mario）。向前移动一个网格，小马里奥需要消耗 $1$ 个游戏刻，而超级马里奥和火焰马里奥则需要消耗 $2$ 个游戏刻。马里奥只有在移动结束时才被视为到达了某个网格，且马里奥无法向后移动（如果向后移动就称不上是速通了）。

当马里奥到达一个有电锯的网格时，他会触发电锯并受到伤害（电锯是无法避开的）。这会导致以下行为：

• 如果马里奥处于小马里奥形态，他会死亡。
• 如果马里奥处于超级马里奥形态，他会变成小马里奥。
• 如果马里奥处于火焰马里奥形态，他会变成超级马里奥。

当马里奥到达一个有问号方块的网格时，他可以选择是否触发它。如果选择触发，会导致以下行为：

• 如果马里奥处于小马里奥形态，他会变成超级马里奥。
• 如果马里奥处于超级马里奥形态，他会变成火焰马里奥。
• 如果马里奥处于火焰马里奥形态，什么都不会发生。

与电锯和问号方块的交互均消耗 $0$ 个游戏刻。也就是说，当马里奥到达并触发它们时，马里奥会瞬间改变形态并更新他的速度。马里奥不可能触发同一个电锯两次，也不可能触发同一个问号方块两次。

速通玩家现在面临着一个艰难的选择：如何极限优化并决定是否触发每个问号方块。更复杂的是，玩家被允许在关卡开始时选择 $3$ 种马里奥形态中的任意一种。处于小马里奥形态可以让跑得更快，但如果在到达终点前死亡，跑得再快也无济于事。

在最优策略下，是否可能通关？如果可以，成功通关所需的最少游戏刻是多少？

输入格式

第一行输入一个整数 $2 \le N \le 200\,000$。

第二行输入一个长度为 $N$ 的字符串，仅由字符 .、? 和 S 组成。保证第一个和最后一个字符为 .。

输出格式

输出一个整数，表示成功通关所需的最少游戏刻。如果无法通关，则输出 $-1$。

样例

输入样例 1

4
.S..

输出样例 1

4

说明

样例 1 说明：马里奥在第 1 个网格开始时应选择超级马里奥形态。在此形态下，移动一次需要 $2$ 个游戏刻。因此，马里奥在 $2$ 个游戏刻后到达第 2 个网格。电锯瞬间触发，马里奥变成小马里奥。现在他移动一次只需要 $1$ 个游戏刻。他再花 $1$ 个游戏刻到达第 3 个网格，然后再花 $1$ 个游戏刻到达第 4 个（即最后一个）网格。因此，他总共需要 $2 + 1 + 1 = 4$ 个游戏刻。

输入样例 2

6
.?.?S.

输出样例 2

6

输入样例 3

7
.SS?SS.

输出样例 3

-1