Finding Amsterdam Stock Exchange
Ian and Sylvia are planning a visit to Amsterdam. They want to plan their sight seeing route. Sylvia is reading from the touristic guide and Ian is writing the list with sights.
Sylvia is giving Ian 2 commands:
- Add <sight> -> to add this sight on top of the visiting stack of sights to be planned for visit.
- Remove -> to move the sight on top of the visiting stack in their itinerary.
Ian wants to be able to also add, at the end of the day, a visit to the Amsterdam Stock Exchange Building, as it is the oldest modern exchange in the world, built in 1602.
To be able to do this, he wants to optimize the route that they are planning, without Sylvia's knowledge.
Whenever she is not watching, he can rearrange the stack of sights, so that, if Sylvia is asking to move the top sight to the itinerary, the itinerary list will still have the optimal path.
Tell Ian the minimum number of times he needs to reorder the sights so that he can achieve his goal.
Sights are numbered from 1 to n, in the order of the optimal path that Ian wants to take.
It is guaranteed that a sight will be added, before it is needed for the sight to be moved to the itinerary.
Clarifications Optimal path is the path from 1 n Amsterdam Stock Exchange is considered to be the sight with number n. You have a time limitation of 60 minutes.
Input :
The first line of input contains the integer n (1 <= n <= 10^6) — the number of sights to be planned Each of the next 2n lines of input starts with a string "add" or "remove".
If the line starts with the "add", an integer x (1 <= x <= n) follows, indicating that Ian should add the sight with number x to the top of the stack.
It is guaranteed that exactly n lines contain "add" operations, all the sights added are distinct, and n lines contain "move" operations.
It is also guaranteed that a sight is always added before it is required to be moved.
Output:
Print the minimum number of times Ian needs to reorder the sights to successfully achieve his goal.
Examples:
Input:
3
add 1
remove
add 2
add 3
remove
remove
Output:
should be 1.
Note In the first sample, Ian should reorder the sights after adding sight 3 to the stack.
Input:
7
add 3
add 2
add 1
remove
add 4
remove
remove
remove
add 6
add 7
add 5
remove
remove
remove
For this, output should be 2.
Note: In the second sample, Ian should reorder the sights after adding sight 4 and sight 7 to the stack.