题目内容

你面前有一个垂直的存储通道，只能从顶端放入或取出物品。通道内初始没有物品。

共有 n 个物品，它们的编号分别为 1 到 n。现在你按顺序执行 2n 次操作，操作分为两种：

• 放入：将一个指定编号的物品从通道顶端放入；
• 取出：从通道顶端取出当前最靠外的一个物品。

你的目标是让取出的物品顺序恰好为 1, 2, \dots, n。在任意一次放入操作结束后，你可以立即执行一次“整理”：将通道内当前所有物品按编号从小到大重新摆放，使得编号最小的物品位于顶端，编号最大的物品位于底端。整理不会改变物品集合，仅改变它们的相对顺序。

已知整个操作序列一定存在一种整理方案使得取出顺序满足要求。你需要求出为了按 1 到 n 的顺序取出所有物品，最少需要进行多少次整理。

物品总数 n 满足 $1 \le n \le 10^5$，物品编号的绝对值不超过 $10^9$（实际上编号即为 1 到 n）。

输入描述

第一行输入一个整数 n，代表物品总数。 接下来 2n 行，每行描述一个操作。若为一个字符串 push 后跟一个整数 v，表示放入编号为 v 的物品；若为字符串 pop，表示从顶端取出一个物品。

输出描述

输出一个整数，表示最少需要进行整理的次数。

样例1

输入

1
push 1
pop

输出

0

说明

只有一个物品，编号为 1。放入后直接弹出，弹出顺序为 1，符合要求，不需要进行整理。因此最少整理次数为 0。

样例2

输入

3
push 3
push 2
push 1
pop
pop
pop

输出

0

说明

依次放入 3、2、1 后，通道内从底到顶为 $[3, 2, 1]$，顶端为 1。 弹出时依次得到 1、2、3，恰好满足要求，不需要整理，答案为 0。

样例3

输入

4
push 2
push 3
push 1
pop
pop
push 4
pop
pop

输出

2

说明

初始需要弹出的编号 $need=1$。 操作序列及栈状态：

• push 2: 栈 $[2]$
• push 3: 栈 $[2,3]$
• push 1: 栈 $[2,3,1]$
• pop: 栈顶为 1，弹出 1，$need$ 变为 2，栈变为 $[2,3]$
• pop: 栈顶为 3，不等于 2，需要整理。假设在前一次 push（即 push 1）后整理，栈变为有序 $[1,2,3]$，此时弹出 2（并假设 1 已被弹出），$need$ 变为 3，剩余栈 $[3]$。整理次数加 1。
• push 4: 栈 $[3,4]$
• pop: 栈顶为 4，不等于 3，需要整理。在 push 4 后整理，栈变为 $[3,4]$，弹出 3，$need$ 变为 4，栈 $[4]$
• pop: 弹出 4，$need$ 变为 5。 总共整理 2 次，这是最少的整理次数。

样例4

输入

5
push 2
push 3
push 1
pop
pop
push 4
push 5
pop
pop
pop

输出

2

说明

$need$ 初始为 1。

• push 2, 3, 1 后栈为 $[2,3,1]$，pop 得 1。
• 下一次 pop 需要 2，但栈顶为 3，需整理（第 1 次）。在 push 1 后整理，栈变为 $[1,2,3]$，弹出 2，剩余 $[3]$。
• push 4,5，栈变为 $[3,4,5]$。
• pop 需要 3，栈顶为 5，需整理（第 2 次）。在 push 5 后整理，栈变为 $[3,4,5]$，依次弹出 3,4,5 即可。 总计整理 2 次。