3308 - 大根堆建堆(模板4)

通过次数

1

提交次数

5

时间限制 : 1 秒
内存限制 : 128 MB

输入一组正整数,运用大根堆排序。 然后再输出一序列的数字,当数字大于0时,采取插入操作,当数字为-1时,进行根节点的删除操作。 比如输入6个数字8 6 2 5 9 4,采用小根堆排序时,排序树为:

      9
     /  \
    8    4
  /  \  /
 5   6  2

然后我们输入-1 3 7 -1,代表先对堆进行一次删除操作,再插入数字3和7,然后再进行一次删除操作。

删除根节点9之后为:

      8
     /  \
    6    4
  /  \
 5   2

插入3之后为:

      8
     /  \
    6    4
  /  \   /
 5   2   3

插入7之后为:

      8
     /  \
    6    7
  /  \   / \
 5   2   3  4

再次删除根节点8为:

      7
     /  \
    6    4
  /  \   / 
 5   2   3

输出为7 6 4 5 2 3.

输入

第一行输入两个数n和m。 第二行输入n个正整数,用空格隔开。 后面有m行整数,代表插入和删除。

输出

一行数字,代表在剩余的堆中,从根节点开始到叶节点,按层从左到右排序的节点序列。

样例

输入

6 4
8 6 2 5 9 4
-1 3 7 -1

输出

7 6 4 5 2 3