题解

题面描述

有一个栈中有 $n$ 个元素，这 $n$ 个元素就是 $1$ 到 $n$。现在共有 $2n$ 条指令，有两种指令：

• 指令一: push val，往栈压入元素 $val$；
• 指令二: pop，弹出栈顶元素。

你想依次从栈中 pop 出 $1$ 到 $n$，你可以在每一次 push 操作执行完毕后，对栈里的元素进行重新排序（从栈顶到栈底，按从小到大的顺序）。

题目内容

有一个栈中有$n$个元素，这$n$个元素就是$1$到$n$。现在共有$2*n$条指令，有两种指令:

• 指令一: $push\ val$，往栈压入元素 $val$ ;
• 指令二: $pop$，弹出栈顶元素;

你想依次从栈中 $pop$出$1$~$n$，你可以在每一次指令一执行完毕后，对栈里的元素进行重新排序(从栈顶到栈底、从小到大排序)。

为了顺利 $pop$出$1$~$n$，最少需要进行多少次重新排序。

保证执行 $pop$操作的时候，栈非空，且一定存在一组可行解

输入描述

第一行输入一个整数$n(1≤n≤10^5)$代表元素数量。

此后$2×n$行，每行先输入一个字符串$s$:

如果$s= push$，在同一行上输入一个整数$val (1≤val ≤n)$代表一次指令一;

如果$s= pop$，代表一次指令二。

输出描述

在一行上输出一个整数，代表最少需要进行的重新排序次数。

样例1

输入

3
push 1
pop
push 2
push 3
pop
pop

输出

1

说明

我们要按照顺序拿到$1$~$n$。$push\ 1$，此时栈顶为$1$。$pop$，我们可以拿到$1$，符合要求。$push\ 2$和$push\ 3$，栈里面的元素为$2，3。3$在栈顶。$pop$，如果直接$pop$会拿到$3$，此时我们应该要拿$2$，所以要进行一次排序操作。排序后元素变成3，2。2在栈顶。此时可以拿到2。$pop$，此时可以拿到$3$。进行1次排序就按照顺序拿到了$1$~$n$。

样例2

输入

5
push 1
push 2
push 3
pop
pop
push 4
push 5
pop
POP
PoP

输出

2

说明

$push 1,push 2,push 3$后,栈内元素为{$1,2,3$}，栈顶为$3$。要按照顺序拿到$1$~$n$。下一个操作是$pop$。这时候就需要排序了，排序后变成{$3,2,1$}栈顶为$1$。$pop$，拿到$1$。$pop$拿到2。$push\ 4,push\ 5$栈内元素变成{$3,4,5$}栈顶是$5$，又进行排序，后变成{$5,4,3$}栈顶是$3$。$pop$拿到$3$，$pop$拿到$4$，$pop$拿到$5$。进行$2$次排序就按照顺序拿到了$1$~$n$。