B - Piano 3 Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 200 点

問題文

高橋君は、横一列に並んだ 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

Score : 200 points

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