Fair Photography

Farmer John의 $N$마리 소($1 \le N \le 100{,}000$)가 길게 늘어선 울타리 위 여러 위치에 서 있다. $i$번째 소는 좌표 $x_i$($0$ 이상 $10^9$ 이하 정수)에 서 있고, 품종 $b_i$는 Guernsey G 또는 Holstein H이다. 두 소는 같은 위치에 서 있지 않다.

FJ는 연속된 구간의 소들을 사진에 담으려 한다. 사진에 등장하는 품종마다 마리 수가 같아야 한다. 한 품종만 있어도 된다. 예를 들어 Holstein만 27마리인 사진은 가능하고, Holstein 27마리와 Guernsey 27마리도 가능하지만, Holstein 10마리와 Guernsey 9마리는 불가능하다.

좌표 순으로 연속된 구간 가운데 조건을 만족하는 사진의 크기 최댓값을 구하라. 크기는 사진에 포함된 소들의 최대 좌표와 최소 좌표의 차이다. 소 한 마리만 찍는 사진도 가능하며, 그때 크기는 $0$이다.

첫 줄에 $N$이 주어진다.

다음 $N$줄의 $i$번째 줄에 $x_i$와 $b_i$가 주어진다.

조건을 만족하는 사진 크기의 최댓값을 한 줄에 출력한다.

좌표 순으로 정렬한 뒤 Guernsey를 $+1$, Holstein을 $-1$로 두고 누적합이 같은 두 위치 사이 구간은 두 품종 수가 같다. 같은 품종만 있는 연속 구간도 항상 유효하다. 두 경우를 모두 보면 된다.