在一种著名的查找 k 阶统计量的算法中,我们应该将所有元素分为五个连续元素的组,并找到每五个元素的中位数。中位数称为排序数组的中间元素(它是五个数组中的第三大元素)。为了提高现代显卡上算法的性能速度,您应该能够找到数组中每五个数组中的中位数之和。
排序的 k 元素集 S = {a1, a2, ..., ak} 的中位数之和,其中 a1 < a2 < a3 < ... < ak,将被理解为
$$\sum_{i \mod 5 = 3}^{i \leq k} a_{i-1}$$
$$\bmod$$ 运算符代表取余数,即 $$x \mod y$$ 代表 x 除以 y 的余数。
为了快速组织运动测试,需要计算变化组的中位数总和。
输入
第一行包含数字 n (1 ≤ n ≤ 105),即执行的操作数。
然后每 n 行包含三个操作之一的描述:
- add x — 将元素 x 添加到集合中;
- del x——从集合中删除元素x;
- sum — 求该集合的中位数之和。
对于任何 add x 操作,元素 x 确实不包含在操作之前的集合中。
对于任何 del x 操作,元素 x 确实在操作之前包含在集合中。
输入的所有数字均为正整数,不超过 109。
输出
对于每个运算总和,在单行上打印当前集合的中位数总和。如果集合为空,则打印 0。
请不要使用 %lld 说明符在 C++ 中读取或写入 64 位整数。最好使用 cin、cout 流(您也可以使用 %I64d 说明符)。
示例
输入 #1
6 add 4 add 5 add 1 add 2 add 3 sum
输出 #1
3
输入 #2
14 add 1 add 7 add 2 add 5 sum add 6 add 8 add 9 add 3 add 4 add 10 sum del 1 sum
输出 #2
5 11 13