Description

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$.

Input Format

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 Format

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.

4
????

4.1250

Hint

Translated by ChatGPT 5