配点: $300$ 点

問題文

高橋君はペンギンのレース場を作りました。

レース場は $N$ 個の正方形のマスが西から東に一列に並んだ形状をしています。
これらのマスの状態は文字列 $S$ により表され、西から $i$ 番目のマスの状態は $S$ の $i$ 文字目が - なら「雪」、> なら「氷」です。
また、スタート地点は西端のマスの西の端、ゴール地点は東端のマスの東の端です。

高橋くんのペンギンが、スタート地点からゴール地点を目指して東に進みます。
ペンギンは、雪マスを $1$ マス通過するのに $1$ 秒、氷マスを $1$ マス通過するのに $1/(k+2)$ 秒の時間を要します。
ここで、$k$ はその氷マスの直前に連続して存在する氷マスの個数です。
例えば、雪マスの直後に氷マスが $2$ つ存在する場合、$1$ つ目の氷マスは $1/2$ 秒、$2$ つ目の氷マスは $1/3$ 秒で通過します。

ペンギンがスタートする前に、高橋君は雪マスのうち $1$ つを氷マスに変えることができます。
ペンギンがスタート地点を出発してからゴール地点に到達するまでに最小で何秒かかるでしょうか？

制約

• $3 \\leq N \\leq 100 \\ 000$
• $S$ は -, > で構成される長さ $N$ の文字列
• $S_1 = S_2 = S_{N-1} = S_N =$ -
• $S$ において、- は必ず別の - と隣接して現れる

入力

入力は以下の形式で標準入力から与えられる。

$N$ $S$

出力

ペンギンがゴール地点に到達するのに要する秒数の最小値を出力せよ。
ジャッジの出力との相対誤差または絶対誤差が $10^{-8}$ 以下であれば正解となる。

入力例 1

5
-->--

出力例 1

3.83333333333333

西から $4$ 番目のマスを雪マスから氷マスに変えると、レース場は -->>- となります。
このとき、ペンギンは西から $1, 2, 3, 4, 5$ 番目のマスの通過にそれぞれ $1, 1, 1/2, 1/3, 1$ 秒、合計で $23/6 = 3.83333333...$ 秒を要し、これが最短です。

入力例 2

7
-------

出力例 2

6.5

どのマスを雪マスから氷マスに変えても、ペンギンは $13/2 = 6.5$ 秒でゴールします。

入力例 3

10
-->>>-->--

出力例 3

6.78333333333333

西から $2$ 番目または $6$ 番目のマスを雪マスから氷マスに変えると、ペンギンは $407/60 = 6.783333333...$ 秒でゴールすることができます。