프로그램 명: usa_fairphoto
제한시간: 1 초

농부 존의 N마리의 젖소들은 직선 모양의 울타리에 서있다. 각 소들은 건지종이거나 홀스타인종이다.

농부 존은 연속한 구간의 소들을 찍으려고 하는데 찍힌 사진에는 사진에 포함된 종류의 소들이 골고루 들어갔으면 한다. 즉, 홀스타인종의 소만 있는 사진이나 건지종의 소가 27마리 있고 홀스타인종의 소가 27마리 있는 사진은 찍을 수 있지만 건지종의 소가 10마리 있고 홀스타인종의 소가 9마리 있는 사진은 찍을 수 없다.

한편, 농부 존은 농장의 광활함을 표현하기 위해 최대한 넓은 사진을 찍으려고 한다. 농부 존을 도와 얼마나 넓은 사진을 찍을 수 있는지 구하는 프로그램을 작성하여라. 단, 사진의 양 끝에 젖소가 걸쳐있어야 한다.

입력 형식

출력 형식

농부 존이 찍을 수 있는 가장 넓은 사진의 길이를 출력한다.

입출력 예

입력 

6 
4 G 
10 H 
7 G 
16 G 
1 G 
3 H 

출력 

7

예제 설명

3 ~ 10 범위의 소를 찍으면 건지종 소 2마리와 홀스타인종 소 2마리를 찍으면서 가장 넓게 찍을 수 있다.
Farmer John's N cows (1 <= N <= 100,000) are standing at various positions along a long one-dimensional fence. The ith cow is standing at position x_i (an integer in the range 0...1,000,000,000) and has breed b_i (either 'G' for Guernsey or 'H' for Holstein). No two cows occupy the same position.

FJ wants to take a photo of a contiguous interval of cows for the county fair, but we wants all of his breeds to be fairly represented in the photo. Therefore, he wants to ensure that, for whatever breeds are present in the photo, there is an equal number of each breed (for example, a photo with all Holsteins is ok, a photo with 27 Holsteins and 27 Guernseys is ok, but a photo with 10 Holsteins and 9 Guernseys is not ok).

Help FJ take his fair photo by finding the maximum size of a photo that satisfies FJ's constraints. The size of a photo is the difference between the maximum and minimum positions of the cows in the photo. It is possible that FJ could end up taking a photo of just a single cow, in which case this photo would have size zero.

입력

출력

* Line 1: A single integer indicating the maximum size of a fair photo.

입출력 예

입력

6
4 G
10 H
7 G
16 G
1 G
3 H

출력

7

INPUT DETAILS:

There are six cows with breeds (from left to right) G, H, G, G, H, G.

OUTPUT DETAILS:

The largest fair photo Farmer John can take is of the middle 4 cows, containing 2 Holsteins and 2 Guernseys. 
출처:USACO 2014 US Open, Bronze
번역:functionx
[질/답] [제출 현황] [푼 후(0)]
[ 채 점 ] [홈으로]  [뒤 로]