J. Narrow Bus
time limit per test
0.5 с
memory limit per test
256 megabytes
input
standard input
output
standard output

The narrow bus is so narrow it doesn't have any seats and the passengers have to stand in a row. The bus has two doors that can be used for entering or leaving the bus: one in the front and one in the back. People can't easily swap in the bus because it is too narrow, so the order people are standing in does not change while the bus is running.

At each bus stop, either a single person enters the bus or a single person leaves the bus.

  • If a person wants to enter the bus, they will choose one of the doors to do that. Then this person joins the beginning or the end of the row, according to which door they used to enter.
  • If a person wants to leave at a stop, they will choose the direction with the least amount of people and proceed to that door (in case both directions have the same amount of people, the person chooses the front door). Everyone in that direction will have to get out then as well. No one likes standing outside and waiting so everybody who wants to continue riding the bus will use the other door to get back in. These passengers will enter the bus back in the same order they got out.

Given a description of people entering and leaving the bus, count how many people will have to get out when somebody leaves the bus.

Input

The first line of input contains a single integer n, the number of actions at bus stops (1 ≤ n ≤ 105). The next n lines will contain one of the three types of actions each. The actions happen consecutively as they are given in the input.

  • "F" — a person enters the bus using the front door.
  • "B" — a person enters the bus using the back door.
  • "O i" — the i-th person that has entered the bus today leaves.

Each action happens at a single bus stop. After the action is completed, the bus leaves for the next stop.

Output

Print a single integer for each type "O" query, the number of people who will have to get out and go back in the bus when a person leaves at the stop.

Examples
Input
9
F
B
B
B
B
O 2
F
F
O 4
Output
1
2
Note

In the example, after everyone gets in the bus during the first 5 stops, the people are ordered 1, 2, 3, 4, 5.

At the 6th stop, the 2nd person leaves through the front door and the 1st person is forced to get out of the bus. The 1st person then uses the back door to enter the bus again. The order changes to 3, 4, 5, 1.

During the next two stops two people use the front door to enter the bus, and the order becomes 7, 6, 3, 4, 5, 1.

At the 9th stop, the 4th person leaves through the back door and now the 5th and the 1st person are forced to get out of the bus. They then use the front door to get back in the bus. The order changes to 5, 1, 7, 6, 3.