B - 握手の列 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 233 点

問題文

高橋君は、パーティー会場で面白い現象を観察しています。

N 人の参加者が一列に、全員同じ方向（右向き）を向いて並んでおり、左から順に 1, 2, \ldots, N と番号が付けられています。各参加者は自分から見た左手と右手にそれぞれ手袋をはめています。手袋の色は紺色または白色のいずれかです。入力では、紺色を N（Navy）、白色を S（Snow）で表します。

> 注意： 手袋の色を表す文字 N（紺色）と、参加者の人数を表す整数 N は異なるものです。混同しないよう注意してください。

参加者 i の左手の手袋の色は L_i、右手の手袋の色は R_i で与えられます。

全員が同じ方向を向いて一列に並んでいるため、隣り合う2人の参加者が握手をするとき、左側の参加者（番号が小さい方）の右手と、右側の参加者（番号が大きい方）の左手が触れ合います。このとき、触れ合う2つの手袋の色が同じ（紺色同士または白色同士）である場合、これを 気まずい握手 と呼びます。

高橋君は、隣り合う参加者のペアのうち、気まずい握手になるペアの数を知りたいと思っています。

具体的には、i = 1, 2, \ldots, N-1 のそれぞれについて、参加者 i の右手の手袋の色 R_i と参加者 i+1 の左手の手袋の色 L_{i+1} が同じであるかを調べ、同じであるような i の個数を求めてください。

制約

  • 2 \leq N \leq 2 \times 10^5
  • L_i は N または S (1 \leq i \leq N)
  • R_i は N または S (1 \leq i \leq N)

入力

N
L_1 R_1
L_2 R_2
\vdots
L_N R_N
  • 1 行目には、参加者の人数を表す整数 N が与えられる。
  • 続く N 行のうち i 行目 (1 \leq i \leq N) には、参加者 i の左手の手袋の色を表す文字 L_i と右手の手袋の色を表す文字 R_i が、スペース区切りで与えられる。L_i, R_i はそれぞれ N（紺色）または S（白色）のいずれかである。

出力

気まずい握手になる隣り合う参加者のペアの数を 1 行で出力せよ。

入力例 1

4
N S
S N
N N
S S

出力例 1

2

入力例 2

2
N N
N S

出力例 2

1

入力例 3

10
S S
S N
N S
S S
S N
N N
N S
S S
S N
N N

出力例 3

9

Score : 233 pts

Problem Statement

Takahashi is observing an interesting phenomenon at a party venue.

N participants are standing in a line, all facing the same direction (to the right), and are numbered 1, 2, \ldots, N from left to right. Each participant is wearing a glove on their left hand and right hand (from their own perspective). The color of each glove is either navy or white. In the input, navy is represented by N (Navy) and white is represented by S (Snow).

> Note: The character N representing the navy color and the integer N representing the number of participants are different things. Please be careful not to confuse them.

The color of participant i's left-hand glove is given as L_i, and the color of their right-hand glove is given as R_i.

Since all participants are standing in a line facing the same direction, when two adjacent participants shake hands, the right hand of the left participant (the one with the smaller number) and the left hand of the right participant (the one with the larger number) touch each other. If the colors of the two gloves that touch are the same (both navy or both white), this is called an awkward handshake.

Takahashi wants to know the number of adjacent participant pairs that result in an awkward handshake.

Specifically, for each i = 1, 2, \ldots, N-1, check whether the color of participant i's right-hand glove R_i and the color of participant i+1's left-hand glove L_{i+1} are the same, and find the number of such i.

Constraints

  • 2 \leq N \leq 2 \times 10^5
  • L_i is N or S (1 \leq i \leq N)
  • R_i is N or S (1 \leq i \leq N)

Input

N
L_1 R_1
L_2 R_2
\vdots
L_N R_N
  • The first line contains an integer N representing the number of participants.
  • In the following N lines, the i-th line (1 \leq i \leq N) contains the character L_i representing the color of participant i's left-hand glove and the character R_i representing the color of participant i's right-hand glove, separated by a space. Each of L_i and R_i is either N (navy) or S (white).

Output

Print the number of adjacent participant pairs that result in an awkward handshake, in a single line.

Sample Input 1

4
N S
S N
N N
S S

Sample Output 1

2

Sample Input 2

2
N N
N S

Sample Output 2

1

Sample Input 3

10
S S
S N
N S
S S
S N
N N
N S
S S
S N
N N

Sample Output 3

9