冈部和超级黑客达鲁正在堆放和拆除盒子。有n个盒子,编号从1到n。最初堆栈上没有盒子。
Okabe 是一个控制狂,他给了 Daru 2n 个命令:其中 n 个是将一个盒子添加到堆栈顶部,其中 n 个是将一个盒子从堆栈顶部移除并将其扔进垃圾桶。冈部希望达鲁按照从 1 到 n 的顺序扔掉盒子。当然,这意味着 Daru 可能无法执行 Okabe 的某些删除命令,因为所需的框不在堆栈顶部。
这就是为什么 Daru 可以决定等到 Okabe 看向别处,然后以他想要的任何方式重新排序堆栈中的盒子。他可以在 Okabe 命令之间的任何时间点执行此操作,但在执行此操作时他无法添加或删除盒子。
告诉 Daru 他需要重新排序盒子的最少次数,以便他能够成功完成 Okabe 的所有命令。保证每个盒子在需要移除之前都被添加。
输入
输入的第一行包含整数 n (1 ≤ n ≤ 3·105) — 盒子的数量。
接下来的 2n 行输入中的每一行都以字符串“add”或“remove”开头。如果该行以“add”开头,则后面跟着一个整数 x (1 ≤ x ≤ n),表示 Daru 应该将编号为 x 的框添加到堆栈顶部。
保证恰好 n 行包含“添加”操作,所有添加的框都是不同的,并且 n 行包含“删除”操作。还可以保证总是在需要删除盒子之前添加盒子。
输出
打印 Daru 需要重新排序盒子才能成功完成 Okabe 的所有命令的最小次数。
示例
输入 #1
3 add 1 remove add 2 add 3 remove remove
输出 #1
1
输入 #2
7 add 3 add 2 add 1 remove add 4 remove remove remove add 6 add 7 add 5 remove remove remove
输出 #2
2
注意
在第一个示例中,Daru 应在将框 3 添加到堆栈后重新排序框。
在第二个示例中,Daru 应在将框 4 和框 7 添加到堆栈后重新排序框。