CF939E Maximize!

给定一个由正整数组成的多重集 $S$（初始为空）。有两种操作： 1. 向 $S$ 中添加一个正整数，且新添加的整数不小于 $S$ 中的任意数。 2. 找出 $S$ 的一个子集 $s$，使得值 $$ \max(s) - \text{avg}(s) $$ 最大。这里 $\max(s)$ 表示 $s$ 中元素的最大值，$\text{avg}(s)$ 表示 $s$ 中元素的平均值。输出该最大值。

第一行包含一个整数 $Q$（$1 \le Q \le 5 \cdot 10^{5}$），表示操作的数量。 接下来的 $Q$ 行，每行描述一个操作。对于类型为 $1$ 的操作，输入两个整数 $1$ 和 $x$，其中 $x$（$1 \le x \le 10^{9}$）为要加入 $S$ 的数，保证 $x$ 不小于 $S$ 中的任意数。对于类型为 $2$ 的操作，输入一个整数 $2$。 保证第一个操作为类型 $1$，即当出现类型 $2$ 的操作时，$S$ 不为空。

对于每个类型为 $2$ 的操作，按输入顺序输出答案，每个答案占一行。 如果你的每个答案的绝对误差或相对误差不超过 $10^{-6}$，则视为正确。 形式化地，设你的答案为 $a$，标准答案为 $b$，当 $$ \frac{|a-b|}{\max(1, |b|)} \le 10^{-6} $$ 时，答案被认为是正确的。

由 ChatGPT 4.1 翻译