문제
농부 창재의 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
힌트
출처
USACO 2014 US Open Contest Bronze Problem
로그인해야 코드를 작성할 수 있어요.