41002 - 堆箱子

小明和小凯正在堆叠和移走箱子。n(1 ≤ n ≤ 300000)个箱子的编号为从1到n。初始时堆栈中没有箱子。

小明是一个控制狂,他给小凯下达了 2n 条命令:n条命令是在堆顶添加一个箱子,n条命令是从堆顶移走一个箱子。小明希望小凯按照从1到n的顺序移走箱子。

当然,小凯可能无法执行小明的某些移除命令,因为所需箱子此时并不在堆顶。因此小凯需等到小明移开视线,然后以他想要的任何方式重新排列堆栈中的箱子。

问:小凯最少需要进行多少次重排操作,就可以成功完成小明的所有命令。

数据确保每个箱子在被移走前先添加它们。

输入

第一行,一个整数N,为N个箱子;

以下2N行为命令,如 add 2:为添加编号为2的箱子到栈顶,remove:从栈顶取走一个箱子。

输出

一行,一个整数,表示要重排的次数

样例

输入

3
add 1 
remove 
add 2
add 3
remove
remove

输出

1
时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题