시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 150 32 27 45.000%

문제

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

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

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

입력

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

출력

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

예제 입력 1

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

예제 출력 1

11
W3sicHJvYmxlbV9pZCI6IjE3OTciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFkZTBcdWQ2MTVcdWM3YTFcdWQ3OGMgXHVjOTA0XHVjMTFjXHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMxOGNcdWMyZGNcdWFjMjQgXHVkNjhjXHVjN2E1IFx1ZDU2ZFx1YzJiOVx1Yzc3NFx1YjI5NCBcdWQwNzRcdWI3ZmRcdWM1ZDAgXHVkNjhjXHVjNmQwXHViNGU0XHVjNzQ0IFx1YmFhOFx1YzU0NFx1YjE5M1x1YWNlMCBcdWQ1NjhcdWFlZDggXHVjMThjXHViMTQwXHVjMmRjXHViMzAwIFx1Y2RhNFx1Yzc0NCBcdWNkOTRcdWFjZTAgXHViMDljIFx1YjRhNCBcdWQzMmNcdWI0ZTRcdWM1ZDBcdWFjOGMgXHVjMThjXHViMTQwXHVjMmRjXHViMzAwIFx1Y2RhNFx1YzVkMFx1YzExYyBcdWI5YzhcdWM5YzBcdWI5YzkgXHViZDgwXHViZDg0XHVjNWQwIFx1YjA5OFx1YzYyNFx1YjI5NCBcdWJhNjRcdWJjODRcdWI0ZTRcdWM3NzQgXHVkNTVjIFx1YzkwNFx1Yjg1YyBcdWJhYThcdWM3NzRcdWIyOTQgXHViZDgwXHViZDg0XHVjNzQ0IFx1YzU0OFx1YmIzNCBcdWQ1NzRcdWM4ZmNcdWFjZTAgXHVjNzg4XHVjNWM4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM1NDhcdWJiMzRcdWI5N2MgXHVkNTU4XHViMzU4IFx1YzkxMSBcdWQ1NmRcdWMyYjlcdWM3NzRcdWIyOTQgXHVkNTVjIFx1YzkwNFx1Yjg1YyBcdWMxMjAgXHVjMGMxXHVkMGRjXHVjNWQwXHVjMTFjIFx1Yzc3NFx1YjRlNCBcdWM5MTEgXHVjNWYwXHVjMThkXHViNDFjIFx1YzBhY1x1Yjc4Y1x1YjRlNFx1Yzc0NCBcdWFkZjhcdWI4ZjkgXHVjOWMwXHVjNWM4XHVjNzQ0IFx1YjU0YywgXHVjNzc0IFx1YWRmOFx1YjhmOVx1YzVkMCBcdWMxOGRcdWQ1NWMgXHViMGE4XHViMTQwXHVjNzU4IFx1YzIxOFx1YWMwMCBcdWFjMTlcdWM3NDAgXHVhZGY4XHViOGY5XHVjNzc0IFx1YWMwMFx1YzdhNSBcdWJjZjRcdWFlMzAgXHVjODhiXHViMmU0XHViMjk0IFx1YWM4M1x1Yzc0NCBcdWM1NGNcdWM1NThcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWRmOFx1Yjc5OFx1YzExYyBcdWQ1NmRcdWMyYjlcdWM3NzRcdWIyOTQgXHVkMzJjXHViNGU0XHVjNzc0IFx1ZDU1YyBcdWM5MDRcdWI4NWMgXHVjMTMwXHVjNzQ0IFx1YjU0YyBcdWM3MDRcdWM3NTggXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjI5NCBcdWFkZjhcdWI4ZjkgXHVjOTExIFx1YWMwMFx1YzdhNSBcdWFlMzhcdWM3NzRcdWFjMDAgXHVhZTM0IFx1YWRmOFx1YjhmOVx1Yzc0NCBcdWNjM2VcdWFjZTBcdWM3OTAgXHVkNTVjXHViMmU0LiBcdWFjMDBcdWM3YTUgXHVhZTM4XHVjNzc0XHVhYzAwIFx1YWUzOFx1YjJlNFx1YjI5NCBcdWM3NThcdWJiZjhcdWIyOTQgXHVhZGY4XHViOGY5XHVjNWQwXHVjMTFjIHhcdWM4OGNcdWQ0NWNcdWFjMDAgXHVhYzAwXHVjN2E1IFx1Yzc5MVx1Yzc0MCBcdWMwYWNcdWI3OGNcdWFjZmMgXHVkMDcwIFx1YzBhY1x1Yjc4Y1x1Yzc1OCBcdWNjMjhcdWM3NzRcdWFjMDAgXHVhYzAwXHVjN2E1IFx1ZDA2Y1x1YjJlNFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1YzZiMFx1YjlhY1x1YjI5NCBcdWM3NzRcdWI3ZjAgXHVkNTZkXHVjMmI5XHVjNzc0XHViOTdjIFx1YjNjNFx1YzY0MFx1YzhmY1x1Yzc5MC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkNTVjIFx1YzkwNFx1Yjg1YyBcdWMxMjAgXHVkMzJjXHViNGU0XHVjNzU4IFx1YzIxOCBOKDEgJmxlOyBOICZsZTsgMSwwMDAsMDAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWRmOCBcdWIyZTRcdWM3NGMgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViMGE4XHViMTQwXHVjNzU4IFx1YzEzMVx1YmNjNFx1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHVjMjE4KFx1YjBhOFx1Yzc5MFx1YjI5NCAwLCBcdWM1ZWNcdWM3OTBcdWIyOTQgMSlcdWM2NDAgXHVjNzc0XHViNGU0XHVjNzc0IFx1YzExY1x1Yzc4OFx1YjI5NCB4XHVjODhjXHVkNDVjXHVhYzAwIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiB4XHVjODhjXHVkNDVjXHViMjk0IDAgXHVjNzc0XHVjMGMxIDEsMDAwLDAwMCwwMDAgXHVjNzc0XHVkNTU4XHVjNzc0XHViMmU0LiZuYnNwO1x1YWMwMSBcdWMxMzFcdWJjYzRcdWM3NTggXHVkMzJjXHVjNzQwIFx1Y2Q1Y1x1YzE4YyAxXHViYTg1IFx1Yzc3NFx1YzBjMSBcdWM4NzRcdWM3YWNcdWQ1NThcdWFjZTAsIFx1YWMxOVx1Yzc0MCB4XHVjODhjXHVkNDVjXHVjNWQwIFx1YzExYyBcdWM3ODhcdWIyOTQgXHVkMzJjXHVjNzQwIFx1YzVjNlx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWM4NzBcdWFjNzRcdWM3NDQgXHViOWNjXHVjODcxXHVkNTU4XHViMjk0IFx1YWRmOFx1YjhmOSBcdWM5MTEgXHVhYzAwXHVjN2E1IFx1YWUzNCBcdWFkZjhcdWI4ZjlcdWM3NTggXHVhZTM4XHVjNzc0XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxNzk3IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQmFsYW5jZWQgTGluZXVwIiwiZGVzY3JpcHRpb24iOiI8cD5GYXJtZXIgSm9obiBoYXMgZGVjaWRlZCB0byB0YWtlIGEgZmFtaWx5IHBvcnRyYWl0IG9mIHNvbWUgKG1heWJlIGFsbCkgb2YgdGhlIGNvd3MuIEluIG9yZGVyIHRvIHRha2UgdGhlIHBvcnRyYWl0LCBGSiBoYXMgYXJyYW5nZWQgYWxsIE4gKDEgJmxlOyBOICZsZTsgMSwwMDAsMDAwKSBjb3dzIGluIGEgc3RyYWlnaHQgbGluZS4gRWFjaCBjb3cgaXMgbGFiZWxlZCB3aXRoIGl0cyB4IGNvb3JkaW5hdGUgKHJhbmdlOiAwLi4xLDAwMCwwMDAsMDAwKSBvbiB0aGUgbGluZSBhcyB3ZWxsIGFzIGl0cyBicmVlZCAoMCBvciAxKS48XC9wPlxyXG5cclxuPHA+T3ZlciB0aGUgeWVhcnMsIEZKIGhhcyBkb25lIHNvbWUgY3JhenkgdGhpbmdzLCBhbmQgdGhpcyBhY3Rpdml0eSBpcyBubyBleGNlcHRpb24uIEhlIHdpbGwgb25seSBwaG90b2dyYXBoIG9uZSBncm91cCBvZiBjb3dzLCBhbmQgdGhhdCBncm91cCBtdXN0IGJlICZxdW90O2JhbGFuY2VkJnF1b3Q7LiBBIGNvbnRpZ3VvdXMgZ3JvdXAgb2YgY293cyBpcyAmcXVvdDtiYWxhbmNlZCZxdW90OyBpZiBpdCBjb250YWlucyB0aGUgc2FtZSBudW1iZXIgb2YgY293cyBmcm9tIGVhY2ggb2YgdGhlIHR3byBicmVlZHMuPFwvcD5cclxuXHJcbjxwPkRldGVybWluZSB0aGUgd2lkZXN0IGV4cGFuc2Ugb2YgY293cyB0aGF0IG1pZ2h0IGhhdmUgdG8gZml0IGluIG9uZSBwaG90b2dyYXBoLiBUaGUgbGVuZ3RoIG9mIGEgYmFsYW5jZWQgZ3JvdXAgaXMgdGhlIGRpZmZlcmVuY2UgaW4geCB2YWx1ZXMgYmV0d2VlbiB0aGUgbGVmdC1tb3N0IGFuZCByaWdodC1tb3N0IGNvd3MgaW4gdGhlIGdyb3VwLjxcL3A+XHJcblxyXG48cD5BdCBsZWFzdCBvbmUgY293IG9mIGVhY2ggYnJlZWQgYXBwZWFycyBpbiB0aGUgaW5wdXQsIGFuZCBubyB0d28gY293cyBzaGFyZSB0aGUgc2FtZSB4IGNvb3JkaW5hdGUuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD4qIExpbmUgMTogQSBzaW5nbGUgaW50ZWdlcjogTjxcL3A+XHJcblxyXG48cD4qIExpbmVzIDIuLk4gKyAxOiBFYWNoIGxpbmUgY29udGFpbnMgdHdvIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2VycyB0aGF0IGRlc2NyaWJlIGEgc2luZ2xlIGNvdyBjb250YWluaW5nIHJlc3BlY3RpdmVseTogYSBicmVlZCBJRCBhbmQgYW4geCBjb29yZGluYXRlPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+KiBMaW5lIDE6IEEgc2luZ2xlIGludGVnZXIgc3BlY2lmeWluZyB0aGUgc2l6ZSBvZiB0aGUgbGFyZ2VzdCBjb250aWd1b3VzIGJhbGFuY2VkIGdyb3VwIG9mIGNvd3MuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

Olympiad > USA Computing Olympiad > 2006-2007 Season > USACO March 2007 Contest > Silver 2번

  • 문제를 번역한 사람: author6
  • 데이터를 추가한 사람: isku
  • 빠진 조건을 찾은 사람: kks227
  • 잘못된 조건을 찾은 사람: leehosu01
  • 문제의 오타를 찾은 사람: lyzqm