‹ 上一题 下一题 ›

s09227. 柜台对账单 未做

1000 ms 256 MB 测试点 10 S-06·贪心进阶与反悔贪心中位数进出堆

题目描述

票册初始为空,共进行 次操作,操作分为两种:

  • 1 x:放入一张票面为 的票(票面可以重复);
  • 2 x:取出一张票面为 的票;若票册中没有票面为 的票,则本次操作无效。

全部操作结束后输出三行对账单:第一行为票册当前票面的上中位数(偶数张时取中间两个中较大的;票册为空输出 );第二行为有效取票操作的次数;第三行为所有被有效取走的票面之和。

输入格式

第一行一个整数 。

接下来 行,每行是 1 x 或 2 x。

输出格式

三行,依次为上中位数、有效取票次数、被取走的票面之和。

样例 1

样例

输入
7
1 5
1 3
1 8
2 3
1 4
2 9
1 6
输出
6
1
3

2 9 时票册中没有 ,该操作无效。最终票册为 ,偶数张取中间两个中较大的 。

样例 2

第五次操作 2 7 时票册已空,无效;有效取走 共三张,和为 ;最终票册为 ,上中位数为 。

数据范围

;。第三行可能超过 32 位整数范围。

输入
输出

            
答案