Album of Numbers

Johnny is a collector of numbers. He has a large album with them, which he keeps updating by inserting new numbers and deleting old ones.

This album is Johnny's most prized treasure, so he wants to be sure that no one will ever replace his numbers with different ones. He therefore maintains a checksum for the album, determined as follows. He considers all distinct nonempty subsets of the numbers in the album, finds the minimum of each subset, and then calculates the arithmetic mean of these minima.

Because a number may appear multiple times in the album, the subsets are multisets: each number may appear in a subset multiple times, but no more than it appears in the whole album. Two multisets are equal if and only if every number has the same multiplicity in both. For instance, the album $\{1, 2, 2, 5\}$ has the following 11 distinct subsets: $\{1\}$, $\{1, 2\}$, $\{1, 2, 2\}$, $\{1, 2, 2, 5\}$, $\{1, 2, 5\}$, $\{1, 5\}$, $\{2\}$, $\{2, 2\}$, $\{2, 2, 5\}$, $\{2, 5\}$, and $\{5\}$.

The album changes often, which makes maintaining the checksum by hand tedious. Write a program that reads the number of updates and their descriptions, determines the checksum after each operation, and prints the checksums.

The first line contains a single positive integer $n$ ($1 \le n \le 250\,000$), the number of updates. Each of the next $n$ lines contains a sign, either + or -, a single space, and a number $a_i$ ($1 \le a_i \le 1\,000\,000\,000$). A + inserts $a_i$ into the album, and a - removes one occurrence of $a_i$ from the album.

The album is initially empty. It is always nonempty after an operation, and only numbers present in the album are ever deleted.

Print exactly $n$ lines. The $i$-th line contains the checksum after the $i$-th update. An answer is accepted if the absolute or relative error of each checksum does not exceed $10^{-6}$.

In the first sample, after all the insertions, the album contains $\{1, 2, 2, 5\}$. At that point Johnny considers the 11 subsets listed above. Their minima are 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 5. Hence the checksum is $\frac{19}{11}\approx 1.727272727$.