Postcard Orientation Expectation

Fedor is an avid traveler and has collected many postcards. Each postcard has a unique picture on the front side and address/text fields on the back. Unfortunately, some postcards in his single stack (held in his hand) are turned the wrong way (upside down) so that the back is facing up. At a party, Fedor wants to display all his postcards on the table with the picture side up. Rather than inspecting and flipping each postcard individually, he uses the following randomized process:

Let \(n\) be the number of postcards remaining in his hand. Fedor chooses an integer \(k\) uniformly at random from \(1\) to \(n\) and removes the top \(k\) postcards from the stack. He then looks at the topmost postcard from these \(k\) postcards. If it is oriented incorrectly (i.e. back side up), he flips the entire block of \(k\) postcards (this operation both reverses the order and changes the orientation of each postcard). If the top postcard is already correct, he leaves the block as is. He then places these \(k\) postcards on the table (without any further rotation). If there are still postcards in his hand, he repeats the process.

After the procedure, some postcards on the table might still be with the back side up. Given the initial configuration of the postcards, where 1 indicates that a postcard is oriented correctly (picture side up) and 0 means it is upside down, determine the expected number of postcards on the table that are incorrectly oriented.

Important: In every block that is removed from the hand, the first postcard (i.e. the top card of that block) always ends up correctly oriented because:

• If it was originally 0, the block is flipped making it 1.
• If it was originally 1, no flip occurs and it remains 1.

For the remaining postcards in the block (if any), their final orientation depends on whether the block was flipped. Specifically, if the block's initial top postcard was 1, the block is not flipped so each remaining postcard keeps its original state. However, if the first postcard was 0, the block is flipped and therefore each remaining postcard has its orientation reversed (i.e. 0 becomes 1 and 1 becomes 0).

Let the initial stack be represented as \(A = [A_1, A_2, \dots, A_n]\) from top to bottom. Then if a block is taken from index \(i\) to \(i+L-1\) where \(L \ge 1\), its contribution to the wrong count is:

• If \(A_i = 1\) (no flip): the number of wrong postcards in the block is \(\#\{j:\ i+1 \le j \le i+L-1 \text{ and } A_j = 0\}\).
• If \(A_i = 0\) (flip): the number of wrong postcards becomes \(\#\{j:\ i+1 \le j \le i+L-1 \text{ and } A_j = 1\}\) since each postcard is inverted.

Your task is to compute the expected total number of postcards that end up being incorrectly oriented on the table.

---

inputFormat

The input consists of two lines:

• The first line contains an integer \(n\) (\(1 \leq n \leq 10^5\)), representing the number of postcards.
• The second line contains \(n\) space-separated integers, each either 0 or 1. Here, 1 denotes that the postcard is initially oriented correctly (picture side up), and 0 denotes that it is upside down.

outputFormat

Output a single number — the expected number of postcards on the table that are incorrectly oriented (back side up). The answer is accepted if its absolute or relative error does not exceed \(10^{-6}\).

sample

1
0

0.000000

</p>