시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 52 26 17 51.515%

문제

소시갤 회장 항승이는 클럽에 회원들을 모아놓고 함께 소녀시대 춤을 추고 난 뒤 팬들에게 소녀시대 춤에서 마지막 부분에 나오는 멤버들이 한 줄로 모이는 부분을 안무 해주고 있었다.

안무를 하던 중 항승이는 한 줄로 선 상태에서 이들 중 연속된 사람들을 그룹 지었을 때, 이 그룹에 속한 남녀의 수가 같은 그룹이 가장 보기 좋다는 것을 알았다.

그래서 항승이는 팬들이 한 줄에 썼을 때 위의 조건을 만족하는 그룹 중 가장 길이가 긴 그룹을 찾고자 한다. 가장 길이가 길다는 의미는 그룹에서 x좌표가 가장 작은 사람과 큰 사람의 차이가 가장 크다는 것이다. 우리는 이런 항승이를 도와주자.

입력

첫째 줄에는 한 줄로 선 팬들의 수 N(1≤N≤1,000,000)이 주어진다. 그 다음 N개의 줄에는 남녀의 성별을 나타내는 수(남자는 0, 여자는 1)와 이들이 서있는 x좌표가 공백으로 구분되어 주어진다. x좌표는 0 이상 1,000,000,000 이하이다.

출력

조건을 만족하는 그룹 중 가장 긴 그룹의 길이를 출력한다.

예제 입력

7
0 11
1 10
1 25
1 12
1 4
0 13
1 22

예제 출력

11

힌트