2791 : 젖소 사진 찍기
- 제한시간
- 1000 ms
- 메모리제한
- 128 MB
- 해결횟수
- 15 회
- 시도횟수
- 211 회
문제
농부 창재의 N마리의 젖소들은 직선 모양의 울타리에 서있다. 각 소들은 건지종이거나 홀스타인종이다.
농부 창재는 연속한 구간의 소들을 찍으려고 하는데 찍힌 사진에는 사진에 포함된 종류의 소들이 골고루 들어갔으면 한다. 즉, 홀스타인종의 소만 있는 사진이나 건지종의 소만 있는 사진은 찍을 수 있다. 두 종의 소들이 섞여 있는 경우에는 같은 수의 소들이 포함되어야 한다. 예를 들면 건지종의 소가 27마리 있고 홀스타인종의 소가 27마리 있는 사진은 찍을 수 있지만 건지종의 소가 10마리 있고 홀스타인종의 소가 9마리 있는 사진은 찍을 수 없다.
한편, 농부 창재는 농장의 광활함을 표현하기 위해 최대한 넓은 사진을 찍으려고 한다. 농부 창재를 도와 얼마나 넓은 사진을 찍을 수 있는지 구하는 프로그램을 작성하여라. 단, 사진의 양 끝에 젖소가 걸쳐있어야 한다.
입력형식
첫 번째 줄에는 젖소의 수 N(1 ≤ N ≤ 100,000)이 주어진다.
두 번째 줄부터 N개의 줄에는 각 소의 위치를 나타내는 0 이상 1,000,000,000 이하의 정수와 각 소의 종을 나타내는 문자(건지종이면 'G', 홀스타인종이면 'H')가 주어진다.
출력형식
농부 창재가 찍을 수 있는 가장 넓은 사진의 길이를 출력한다.
입력 예6 4 G 10 H 7 G 16 G 1 G 3 H |
출력 예7 |
Hint!
3 ~ 10 범위의 소를 찍으면 건지종 소 2마리와 홀스타인종 소 2마리를 찍으면서 가장 넓게 찍을 수 있다.