시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1.5 초 512 MB 1 1 1 100.000%

문제

JOI 君はふと, 魚を飼おうと思い立った.

JOI 君の家の近所のペットショップに行ったところ,そこでは N 匹の魚が売られていた.i 番目の魚の体 長は Li cm で,色は赤,緑,青のいずれかである.JOI 君はこれらの N 匹の魚のうちから 1 匹以上を家で 飼うことに決めた.

魚を飼うときに注意しなければならないことがある.大きい魚と小さい魚を同時に飼うと,大きい魚が 小さい魚を食べてしまう.具体的には,魚 X の体長が魚 Y の体長の 2 倍以上であるとき,X と Y を同時に 飼うと X が Y を食べてしまう.そのため,このような 2 匹の魚を同時に飼うことはできない.

JOI 君は,飼う魚の色の組合せが何通りありうるのかが気になった.2 つの色の組合せが異なるとは,赤, 緑,青の少なくとも 1 色の魚の数が異なることである.ペットショップで売られている魚の体長と色が与 えられるので,JOI 君が飼う魚の色の組合せとして考えられるものの個数を求めたい.

ペットショップで売られている魚の体長と色が与えられたとき,JOI 君が飼う魚の色の組合せとして考え られるものの個数を出力するプログラムを作成せよ.

입력

標準入力から以下の入力を読み込め.

  • 1 行目には整数 N が書かれている.N はペットショップで売られている魚の数を表す.
  • 1 + i 行目 (1 ≤ i ≤ N) には,整数 Li と文字 Ci が空白を区切りとして書かれている.文字 Ci は R,G,B のいずれかである.これは,i 番目の魚の体長が Li cm であり,Ci が R なら i 番目の魚の色が赤,Ci が G なら i 番目の魚の色が緑,Ci が B なら i 番目の魚の色が青であることを表す.

출력

標準出力に,JOI 君が飼う魚の色の組合せとして考えられるものの個数を 1 行で出力せよ.

제한

  • 1 ≤ N ≤ 500 000 魚の数
  • 1 ≤ Li ≤ 1 000 000 000 i 番目の魚の体長

예제 입력 1

4
10 R
4 G
8 B
5 B

예제 출력 1

6

1 番目の魚は 2 番目の魚を食べてしまうので,これらを同時に飼うことはできない.1 番目と 4 番目,2 番目と 3 番目についても同様である.よって,可能な色の組合せは,「赤 1 匹」「緑 1 匹」「青 1 匹」「赤と青 1 匹ずつ」「緑と青 1 匹ずつ」「青 2 匹」の 6 通りである.

예제 입력 2

10
26 B
10 B
16 G
20 R
6 R
5 G
13 G
40 R
8 R
33 R

예제 출력 2

13