물고기
시간 제한1.5초메모리 제한512 MB
길이와 세 가지 색 중 하나를 가진 물고기 N마리가 주어질 때, 두 마리의 길이 비가 2 이상이 되지 않도록 고를 수 있는 집합이 만드는 색 조합의 수를 센다. 두 색 조합은 빨강, 초록, 파랑 각각의 마릿수가 하나라도 다르면 다른 것으로 본다.
문제
JOI 군은 문득 물고기를 기르고 싶어졌다.
JOI 군의 집 근처 애완동물 가게에 갔더니, 그곳에서는 N마리의 물고기가 팔리고 있었다. i번째 물고기의 몸길이는 Li cm이고, 색은 빨강, 초록, 파랑 중 하나이다. JOI 군은 이 N마리의 물고기 중에서 1마리 이상을 집에서 기르기로 했다.
물고기를 기를 때 주의해야 할 점이 있다. 큰 물고기와 작은 물고기를 동시에 기르면 큰 물고기가 작은 물고기를 먹어버린다. 구체적으로, 물고기 X의 몸길이가 물고기 Y의 몸길이의 2배 이상일 때, X와 Y를 동시에 기르면 X가 Y를 먹어버린다. 따라서 이런 두 물고기를 동시에 기를 수는 없다.
JOI 군은 기를 물고기 색 조합이 몇 가지나 가능한지 궁금해졌다. 두 색 조합이 다르다는 것은 빨강, 초록, 파랑 중 적어도 한 색의 물고기 수가 다르다는 것이다. 애완동물 가게에서 팔리는 물고기의 몸길이와 색이 주어지므로, JOI 군이 기를 물고기의 색 조합으로 생각할 수 있는 것의 개수를 구하려고 한다.
애완동물 가게에서 팔리는 물고기의 몸길이와 색이 주어졌을 때, JOI 군이 기를 물고기의 색 조합으로 생각할 수 있는 것의 개수를 출력하는 프로그램을 작성하시오.
입력
표준 입력에서 다음 입력을 읽는다.
- 1번째 줄에는 정수 N이 쓰여 있다. N은 애완동물 가게에서 팔리는 물고기의 수를 나타낸다.
- 1 + i번째 줄 (1 ≤ i ≤ N)에는 정수 Li와 문자 Ci가 공백으로 구분되어 쓰여 있다. 문자 Ci는 R, G, B 중 하나이다. 이는 i번째 물고기의 몸길이가 Li cm이고, Ci가 R이면 i번째 물고기의 색이 빨강, Ci가 G이면 초록, Ci가 B이면 파랑임을 나타낸다.
출력
표준 출력에, JOI 군이 기를 물고기의 색 조합으로 생각할 수 있는 것의 개수를 1줄로 출력하시오.
제한
- 1 ≤ N ≤ 500 000, 물고기의 수
- 1 ≤ Li ≤ 1 000 000 000, i번째 물고기의 몸길이