시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 256 MB | 485 | 160 | 130 | 41.270% |
소시갤 회장 항승이는 클럽에 회원들을 모아놓고 함께 소녀시대 춤을 추고 난 뒤 팬들에게 소녀시대 춤에서 마지막 부분에 나오는 멤버들이 한 줄로 모이는 부분을 안무 해주고 있었다.
안무를 하던 중 항승이는 한 줄로 선 상태에서 이들 중 연속된 사람들을 그룹 지었을 때, 이 그룹에 속한 남녀의 수가 같은 그룹이 가장 보기 좋다는 것을 알았다.
그래서 항승이는 팬들이 한 줄로 섰을 때 위의 조건을 만족하는 그룹 중 가장 길이가 긴 그룹을 찾고자 한다. 가장 길이가 길다는 의미는 그룹에서 x좌표가 가장 작은 사람과 큰 사람의 차이가 가장 크다는 것이다. 우리는 이런 항승이를 도와주자.
첫째 줄에는 한 줄로 선 팬들의 수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 그 다음 N개의 줄에는 남녀의 성별을 나타내는 수(남자는 0, 여자는 1)와 이들이 서있는 x좌표가 공백으로 구분되어 주어진다. x좌표는 0 이상 1,000,000,000 이하이다. 각 성별의 팬은 최소 1명 이상 존재하고, 같은 x좌표에 서 있는 팬은 없다.
조건을 만족하는 그룹 중 가장 긴 그룹의 길이를 출력한다.
7 0 11 1 10 1 25 1 12 1 4 0 13 1 22
11