Ping-Pong Tube

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 2.0s
Memory limit: 256M

Problem type

Aaron is a professional ping-pong player. To practice, he has a machine that feeds him balls from a giant tube.

This machine is quite peculiar. Each ping-pong ball is either white (W) or orange (O). If the ball being fed is white, it will be fed to Aaron's forehand side. Otherwise, it will be fed to Aaron's backhand side.

The tube needs to be refilled by Aaron after each set. To do this, he inserts a ball of arbitrary colour into either the start (left side) or the end (right side) of the tube. Aaron has N balls and the tube can conveniently fit all of them.

The machine feeds balls from the start of the tube (left side). Currently, Aaron is having trouble with switching from forehand to backhand or vice-versa. He wants to know how many times this will happen during the next set. Can you help him?


for all subtasks,

1 \le N \le 10^6

Subtask 1 [20%]

1 \le N \le 2 \times 10^3

Subtask 3 [80%]

No additional constraints.

Input Specification

The first line of input will contain an integer N.

The next N lines will contain two space-separated characters. The first character is either L or R and the second character is either W or O.

If the first character is L, Aaron inserts the ball at the start of the tube. Otherwise, he inserts the ball at the end of the tube.

Output Specification

Determine the number of times Aaron will have to switch from forehand to backhand or vice versa. Output only this integer.

Sample Input


Sample Output



After all the insertions, the tube looks like:

(\text{start}) [W, O, W, O, O] (\text{end})

Aaron will have to switch from his forehand to his backhand for the second ball, back to his forehand for the third, and to his backhand for the forth. He does not need to switch for the fifth ball.


There are no comments at the moment.