Fish(魚) - joi2012-day1

時間制限: 1.5秒

メモリ制限: 64MB

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

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

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

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

課題

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

制限

`1 \leqq N \leqq 500\,000`	魚の数
`1 \leqq L_i \leqq 1\,000\,000\,000`	`i` 番目の魚の体長

入力

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

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

出力

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

採点基準

採点用データのうち，配点の 10% 分は，N \leqq 100 を満たす．

採点用データのうち，配点の 30% 分は，N \leqq 2\,000 を満たす．

入出力例

入力例1	出力例1
`4 10 R 4 G 8 B 5 B`	`6`

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

入力例2	出力例2
`10 26 B 10 B 16 G 20 R 6 R 5 G 13 G 40 R 8 R 33 R`	`13`