← 返回题目列表

Codeforces · 821/C

C. 冈部和盒子

中文机器翻译题面 查看原题

冈部和超级黑客达鲁正在堆放和拆除盒子。有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 添加到堆栈后重新排序框。