P1365 WJMZBMR Plays osu! / Easy

Original: Maintain Queue, see P1903.

One day WJMZBMR was playing osu, ~~but he is too weak; some parts rely entirely on luck :(~~. Let’s simplify the rules of the game. There are $n$ clicks to make. A success is `o`, a miss is `x`. The score is computed by combos: a combo of length $a$ is worth $a\times a$ points. A combo is a maximal consecutive block of `o`. For example, for `ooxxxxooooxxx`, the score is $2 \times 2 + 4 \times 4 = 4 +16=20$. Some positions are fixed (either `o` or `x`), and some positions are random with $50\%$ chance for each, denoted by `?`. For example, `oo?xx` is a possible input. What is the expected score of this osu game? For `oo?xx`, if `?` is `o`, then it becomes `oooxx` ($9$); if it is `x`, then it becomes `ooxxx` ($4$). The expected value is $(4+9)/2 =6.5$.

The first line contains an integer $n$ ($n\le3\times10^5$), the number of clicks. The next line contains a string, where each character is one of `o`, `x`, `?`.

Output a single floating-point number: the answer. Round to $4$ decimal places. If you are worried about precision, it is recommended to use long double or extended.

Translated by ChatGPT 5