给定一个由正整数组成的多重集 S(最初为空)。有两种查询:
1. 在S中添加一个正整数,新添加的整数不小于其中的任何数字。
2. 找到集合 S 的子集 s,使得值 $$\max(s) - \mathrm{mean}(s)$$ 为最大可能值。这里 max(s) 表示 s 中元素的最大值,$$\operatorname{mean}(s)$$ — s 中数字的平均值。输出 $$\max(s) - \mathrm{mean}(s)$$ 的最大可能值。
输入
第一行包含一个整数 Q (1 ≤ Q ≤ 5·105) — 查询数。
接下来的 Q 行中的每一行都包含查询的描述。对于类型 1 的查询,给出两个整数 1 和 x,其中 x (1 ≤ x ≤ 109) 是应添加到 S 中的数字。保证 x 不小于 S 中的任何数字。对于类型 2 的查询,给出单个整数 2。
保证第一个查询的类型为 1,i。 e.当类型2的查询到来时,S不为空。
输出
按照输入中给出的顺序输出第二类型的每个查询的答案。每个数字应打印在单独的行中。
如果您的每个答案的绝对或相对误差不大于 10 - 6,则您的答案被视为正确。
正式来说,让你的答案是a,陪审团的答案是b。如果 $${ \frac { | 则认为您的答案是正确的a - b | } { \operatorname* { m a x } ( 1, | b | ) } } \leq 1 0 ^ { - 6 }$$。
示例
输入 #1
6 1 3 2 1 4 2 1 8 2
输出 #1
0.0000000000 0.5000000000 3.0000000000
输入 #2
4 1 1 1 4 1 5 2
输出 #2
2.0000000000