2015-16 Woburn Challenge Finals - Senior Division

With intel from the Sacred Tree stolen by hydrated bovine spies, times are getting ever more desperate for the monkeys. The Head-Monkey has decided it's time to send out her own elite special agent – Agent Tiny. Tiny has been ordered to journey to Old MacDonald's farm and perform a precision strike against the cows' military headquarters. For this extremely dangerous mission, Tiny is being outfitted with a sophisticated piece of monkey technology – a fully functional car made of branches and leaves, and powered by banana juice. This car will offer him more than enough speed and maneuverability to infiltrate the barn. Also, it can shoot missiles from its front headlights.

In an effort to ensure that Tiny actually accomplishes something useful with his car in the field, the Head-Monkey has instructed him to take it for a spin on the monkeys' specialized driving course. The course will take place in a very large room, which can be represented as a 2D grid of cells, with some targets on the walls. The rows are numbered in increasing order from North to South (starting from $1$), and similarly the columns are numbered in increasing order from West to East. Tiny will be required to drive around and fire missiles at all of the targets.

Tiny will start in the Northwestern-most cell (in the first row and first column), with his car facing South. Each second, he may either drive to an adjacent cell, or fire a missile in the direction that his car is currently facing. If he chooses to drive, he may do so in one of the four cardinal directions (North, South, East, or West) as long as he stays within the room (he can't drive North from row $1$ or West from column $1$), and his car will be left facing the direction in which he just drove.

The Head-Monkey will add $N$ $(1\le N\le {10}^5)$ targets to the course, one after another, and make Tiny complete the current course after each one is added. Each time, Tiny will have to start in the Northwestern-most cell and hit all of the targets which have been added so far with missiles, in any order. That is, he will have to complete the course $N$ separate times, and on his $i$-th run, he'll be required to hit targets $1\dots i$.

The $i$-th target's position is described by a character $D_i$ (either R or C) and an integer $P_i$ $(1\le P_i\le {10}^9)$. If $D_i=$ R, then the $i$-th target is at the far East end of row $P_i$, meaning that it can be hit by firing a missile Eastward from any cell on row $P_i$. Otherwise if $D_i=$ C, then the $i$-th target is instead at the far South end of column $P_i$. No two targets are at the same location.

To help convince the Head-Monkey of Tiny's driving skills, can you help Tiny determine how quickly the course can be completed each of the $N$ times?

In test cases worth $4/19$ of the points, $N\le 10$ and $P_i\le 10$.
In test cases worth another $7/19$ of the points, $N\le 40$ and $P_i\le 40$.

Input Specification

The first line of input consists of a single integer $N$.
The next $N$ lines each consist of a character and integer $D_i$ and $P_i$, separated by a space, for $i=1\dots N$.

Output Specification

Output $N$ lines, one integer per line. The $i$-th line of output (for $i=1\dots N$) should consist of the minimum number of seconds required to complete the course for the $i$-th time.

Sample Input 1

3
R 3
C 2
C 3

Sample Output 1

4
6
8

Sample Explanation 1

The third and final time that Tiny completes the course, one optimal sequence of actions that he can take is as follows:

• Drive East
• Drive South
• Fire a missile (hitting target $2$)
• Drive East
• Drive South
• Fire a missile (hitting target $3$)
• Drive East
• Fire a missile (hitting target $1$)

Sample Input 2

2
R 1
R 10

Sample Output 2

2
13