WJMZBMR打osu! / Easy

题目背景

原 维护队列 参见 P1903

题目描述

某一天WJMZBMR在打osu~~~但是他太弱逼了,有些地方完全靠运气:( 我们来简化一下这个游戏的规则 有 $n$ 次点击要做,成功了就是 `o`,失败了就是 `x`,分数是按 combo 计算的,连续 $a$ 个 combo 就有 $a\times a$ 分,combo 就是极大的连续 `o`。 比如`ooxxxxooooxxx`,分数就是 $2 \times 2 + 4 \times 4 = 4 +16=20$。 Sevenkplus 闲的慌就看他打了一盘,有些地方跟运气无关要么是 `o` 要么是 `x`,有些地方 `o` 或者 `x` 各有 $50\%$ 的可能性,用 `?` 号来表示。 比如 `oo?xx` 就是一个可能的输入。 那么 WJMZBMR 这场 osu 的期望得分是多少呢? 比如 `oo?xx` 的话,`?` 是 `o` 的话就是 `oooxx`($9$),是x的话就是 `ooxxx`($4$),期望自然就是 $(4+9)/2 =6.5$ 了。

输入输出格式

输入格式


第一行一个整数 $n$($n\le3\times10^5$),表示点击的个数 接下来一个字符串,每个字符都是 `o`,`x`,`?` 中的一个

输出格式


一行一个浮点数表示答案 四舍五入到小数点后 $4$ 位 如果害怕精度跪建议用 long double 或者 extended。

输入输出样例

输入样例 #1

4
????

输出样例 #1

4.1250