离线最小值问题

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

给定集合S={1,2,…,n},以及由n个Insert(x)和m个DeleteMin()运算组成的运算序列。其中n 个Insert(x)运算将集合S={1,2,…,n}中每个数插入动态集合T 恰好一次,DeleteMin()每次删除动态集合T中的最小元素。离线最小值问题要求对于给定的运算序列,计算出每个DeleteMin()运算输出的值。换句话说,要求计算数组out,使第i次DeleteMin()运算输出的值为out[i],i=1,2,…,m。在执行具体计算前,运算序列已给定,这就是问题表述中离线的含义。
对于给定的由n 个Insert(x)和m 个DeleteMin()运算组成的运算序列,用并查集计算出每个DeleteMin()运算输出的值。

Input

输入数据的第1 行有2个正整数n和m(n,m≤1000000),分别表示运算序列由n个Insert(x)和m个DeleteMin()运算组成。接下来的1 行中有n+m个整数(≤1000000)。整数x>0 时表示执行Insert(x)运算;整数x=-1 时表示执行DeleteMin()运算。

Output

将计算出的每个DeleteMin()运算输出的值依次输出。

Sample Input

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

Sample Output

9 10 6 7 8 1

Hint

Source