103691: [Atcoder]ABC369 B - Piano 3

Problem Statement

Takahashi has a piano with $100$ keys arranged in a row. The $i$-th key from the left is called key $i$.

He will play music by pressing $N$ keys one by one. For the $i$-th press, he will press key $A_i$, using his left hand if $S_i=$ L, and his right hand if $S_i=$ R.

Before starting to play, he can place both of his hands on any keys he likes, and his fatigue level at this point is 0. During the performance, if he moves one hand from key $x$ to key $y$, the fatigue level increases by $|y-x|$ (conversely, the fatigue level does not increase for any reason other than moving hands). To press a certain key with a hand, that hand must be placed on that key.

Find the minimum possible fatigue level at the end of the performance.

Constraints

• $1 \leq N \leq 100$
• $1 \leq A_i \leq 100$
• $N$ and $A_i$ are integers.
• $S_i$ is L or R.

Input

The input is given from Standard Input in the following format:

$N$
$A_1$ $S_1$
$A_2$ $S_2$
$\vdots$
$A_N$ $S_N$

Output

Print the minimum fatigue level at the end of the performance.

Sample Input 1

4
3 L
6 R
9 L
1 R

Sample Output 1

11

For example, the performance can be done as follows:

• Initially, place the left hand on key $3$ and the right hand on key $6$.
• Press key $3$ with the left hand.
• Press key $6$ with the right hand.
• Move the left hand from key $3$ to key $9$. The fatigue level increases by $|9-3| = 6$.
• Move the right hand from key $6$ to key $1$. The fatigue level increases by $|1-6| = 5$.
• Press key $9$ with the left hand.
• Press key $1$ with the right hand.

In this case, the fatigue level at the end of the performance is $6+5 = 11$, which is the minimum possible.

Sample Input 2

3
2 L
2 L
100 L

Sample Output 2

98

Sample Input 3

8
22 L
75 L
26 R
45 R
72 R
81 R
47 L
29 R

Sample Output 3

188

问题陈述

高桥有一架带有100个按键的钢琴，这些按键按一行排列。 从左边数第i个键被称为键i。

他将会一个接一个地按下N个键来演奏音乐。 在第i次按下时，他将按下键A_i，如果S_i=L，则使用左手；如果S_i=R，则使用右手。

在开始演奏之前，他可以将双手放在他喜欢的任何键上，此时他的疲劳度为0。 在演奏过程中，如果他将一只手从键x移动到键y，疲劳度将增加|y-x|（相反，除了移动手之外，疲劳度不会因为任何其他原因增加）。 要用一只手按下某个键，那只手必须放在那个键上。

找出演出结束时可能的最小疲劳度。

约束条件

• $1 \leq N \leq 100$
• $1 \leq A_i \leq 100$
• $N$ 和 $A_i$ 都是整数。
• $S_i$ 是 L 或 R。

输入

输入将从标准输入以下格式给出：

$N$
$A_1$ $S_1$
$A_2$ $S_2$
$\vdots$
$A_N$ $S_N$

输出

打印演出结束时的最小疲劳度。

示例输入1

4
3 L
6 R
9 L
1 R

示例输出1

11

例如，演出可以按以下方式进行：

• 最初，将左手放在键3上，右手放在键6上。
• 用左手按下键3。
• 用右手按下键6。
• 将左手从键3移动到键9。疲劳度增加|9-3| = 6。
• 将右手从键6移动到键1。疲劳度增加|1-6| = 5。
• 用左手按下键9。
• 用右手按下键1。

在这种情况下，演出结束时的疲劳度为6+5 = 11，这是可能的最小值。

示例输入2

3
2 L
2 L
100 L

示例输出2

98

示例输入3

8
22 L
75 L
26 R
45 R
72 R
81 R
47 L
29 R

示例输出3

188