Maximize!
Contest: Codeforces Round 464 (Div. 2)
Difficulty rating: 1800
Tags: binary search, greedy, ternary search, two pointers

You are given a multiset S consisting of positive integers (initially empty). There are two kind of queries:

1. Add a positive integer to S, the newly added integer is not less than any number in it.
2. Find a subset s of the set S such that the value $$\max(s) - \mathrm{mean}(s)$$ is maximum possible. Here max(s) means maximum value of elements in s, $$\operatorname{mean}(s)$$ — the average value of numbers in s. Output this maximum possible value of $$\max(s) - \mathrm{mean}(s)$$.

Input format:
The first line contains a single integer Q (1 ≤ Q ≤ 5·105) — the number of queries.

Each of the next Q lines contains a description of query. For queries of type 1 two integers 1 and x are given, where x (1 ≤ x ≤ 109) is a number that you should add to S. It's guaranteed that x is not less than any number in S. For queries of type 2, a single integer 2 is given.

It's guaranteed that the first query has type 1, i. e. S is not empty when a query of type 2 comes.

Output format:
Output the answer for each query of the second type in the order these queries are given in input. Each number should be printed in separate line.

Your answer is considered correct, if each of your answers has absolute or relative error not greater than 10 - 6.

Formally, let your answer be a, and the jury's answer be b. Your answer is considered correct if $${ \frac { | a - b | } { \operatorname* { m a x } ( 1, | b | ) } } \leq 1 0 ^ { - 6 }$$.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Example input:
6
1 3
2
1 4
2
1 8
2

Example output:
0.0000000000
0.5000000000
3.0000000000

Example input:
4
1 1
1 4
1 5
2

Example output:
2.0000000000

Editorial:
Let's first prove some lemmas we will use in the solution. Let a0, ..., an be integers that are at the current moment in S, sorted in increasing order.
Lemma 1. Let the maximum element in optimal s be an. Then the rest of the elements in s form a prefix of a.
Proof: let it be wrong. Let's consider ai (i < n) — the first element of a, that is not in s. We know that in s some element aj is presented (i < j < n). Let's replace in s aj with ai, the average mean(s) will not increase, because ai ≤ aj, max(s) will not change, so max(s) - mean(s) will not decrease.
Lemma 2. Let $$m_i = a_n - \frac{a_n + \sum_{j=0}^{i-1} a_j}{i+1}$$ — the value that we want to maximize in case of s consisting of an, and a prefix of a of length i, i. e. elements a0, ..., ai - 1. A claim: $$$$, where sign(x) denotes the sign of x.
Proof: $$m_{i+1}-m_i=\frac{(-a_n-\sum_{j=0}^{i}a_j)(i+1)+(a_n+\sum_{j=0}^{i-1}a_j)(i+2)}{(i+1)(i+2)}=\frac{a_n+\sum_{j=0}^{i-1}a_j-a_i(i+1))}{(i+1)(i+2)}$$. Because the denominator is always  > 0, then $$$$.
Lemma 3. Let's denote for a fixed n $$f(i) = a_n + \sum_{j=0}^{i-1} a_j - a_i (i+1)$$. f(i) is non-decreasing for increasing i.
Proof: f(i + 1) = f(i) + ai - ai + 1(i + 2) + ai(i + 1) = f(i) - (i + 2)(ai + 1 - ai). ai + 1 - ai ≥ 0, because a is sorted. Then f(i + 1) - f(i) =  - (i + 2)(ai + 1 - ai) ≤ 0, i. e. f(i + 1) - f(i) ≤ 0, this means that f(i) does not decrease when i increases.
Let's solve the problem now. Let's keep the current answer for the query of type 2, let it be ans. When a new operation of type 1 comes, let's update it with the optimal value of max(s) - mean(s) in case max(s) = an, where an is the newly added element. To find this optimal value, let's do binary search for f(i) and find the minimum value of i, such that f(i) ≤ 0. Lemmas prove us that this prefix of length i is optimal for fixed max(s) = an. Now update the value of ans with the value $$a_n - \frac{a_n + \sum_{j=0}^{i-1} a_j}{i+1}$$. To compute the values $$\sum_{j=0}^{i}a_{j}$$ fast, we should maintain the array of prefix sums in a — one more element is added to this array each time a query of type 1 comes.