시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 106 41 31 50.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+XHJcblxyXG48cD5cdWM1NDhcdWJiMzRcdWI5N2MgXHVkNTU4XHViMzU4IFx1YzkxMSBcdWQ1NmRcdWMyYjlcdWM3NzRcdWIyOTQgXHVkNTVjIFx1YzkwNFx1Yjg1YyBcdWMxMjAgXHVjMGMxXHVkMGRjXHVjNWQwXHVjMTFjIFx1Yzc3NFx1YjRlNCBcdWM5MTEgXHVjNWYwXHVjMThkXHViNDFjIFx1YzBhY1x1Yjc4Y1x1YjRlNFx1Yzc0NCBcdWFkZjhcdWI4ZjkgXHVjOWMwXHVjNWM4XHVjNzQ0IFx1YjU0YywgXHVjNzc0IFx1YWRmOFx1YjhmOVx1YzVkMCBcdWMxOGRcdWQ1NWMgXHViMGE4XHViMTQwXHVjNzU4IFx1YzIxOFx1YWMwMCBcdWFjMTlcdWM3NDAgXHVhZGY4XHViOGY5XHVjNzc0IFx1YWMwMFx1YzdhNSBcdWJjZjRcdWFlMzAgXHVjODhiXHViMmU0XHViMjk0IFx1YWM4M1x1Yzc0NCBcdWM1NGNcdWM1NThcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWRmOFx1Yjc5OFx1YzExYyBcdWQ1NmRcdWMyYjlcdWM3NzRcdWIyOTQgXHVkMzJjXHViNGU0XHVjNzc0IFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVjMzdjXHVjNzQ0IFx1YjU0YyBcdWM3MDRcdWM3NTggXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjI5NCBcdWFkZjhcdWI4ZjkgXHVjOTExIFx1YWMwMFx1YzdhNSBcdWFlMzhcdWM3NzRcdWFjMDAgXHVhZTM0IFx1YWRmOFx1YjhmOVx1Yzc0NCBcdWNjM2VcdWFjZTBcdWM3OTAgXHVkNTVjXHViMmU0LiBcdWFjMDBcdWM3YTUgXHVhZTM4XHVjNzc0XHVhYzAwIFx1YWUzOFx1YjJlNFx1YjI5NCBcdWM3NThcdWJiZjhcdWIyOTQgXHVhZGY4XHViOGY5XHVjNWQwXHVjMTFjIHhcdWM4OGNcdWQ0NWNcdWFjMDAgXHVhYzAwXHVjN2E1IFx1Yzc5MVx1Yzc0MCBcdWMwYWNcdWI3OGNcdWFjZmMgXHVkMDcwIFx1YzBhY1x1Yjc4Y1x1Yzc1OCBcdWNjMjhcdWM3NzRcdWFjMDAgXHVhYzAwXHVjN2E1IFx1ZDA2Y1x1YjJlNFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1YzZiMFx1YjlhY1x1YjI5NCBcdWM3NzRcdWI3ZjAgXHVkNTZkXHVjMmI5XHVjNzc0XHViOTdjIFx1YjNjNFx1YzY0MFx1YzhmY1x1Yzc5MC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkNTVjIFx1YzkwNFx1Yjg1YyBcdWMxMjAgXHVkMzJjXHViNGU0XHVjNzU4IFx1YzIxOCBOKDEmbGU7TiZsZTsxLDAwMCwwMDApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhZGY4IFx1YjJlNFx1Yzc0YyBOXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWIwYThcdWIxNDBcdWM3NTggXHVjMTMxXHViY2M0XHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWMyMTgoXHViMGE4XHVjNzkwXHViMjk0IDAsIFx1YzVlY1x1Yzc5MFx1YjI5NCAxKVx1YzY0MCBcdWM3NzRcdWI0ZTRcdWM3NzQgXHVjMTFjXHVjNzg4XHViMjk0IHhcdWM4OGNcdWQ0NWNcdWFjMDAgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIHhcdWM4OGNcdWQ0NWNcdWIyOTQgMCBcdWM3NzRcdWMwYzEgMSwwMDAsMDAwLDAwMCBcdWM3NzRcdWQ1NThcdWM3NzRcdWIyZTQuJm5ic3A7XHVhYzAxIFx1YzEzMVx1YmNjNFx1Yzc1OCBcdWQzMmNcdWM3NDAgXHVjZDVjXHVjMThjIDFcdWJhODUgXHVjNzc0XHVjMGMxIFx1Yzg3NFx1YzdhY1x1ZDU1OFx1YWNlMCwgXHVhYzE5XHVjNzQwIHhcdWM4OGNcdWQ0NWNcdWM1ZDAgXHVjMTFjIFx1Yzc4OFx1YjI5NCBcdWQzMmNcdWM3NDAgXHVjNWM2XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIyOTQgXHVhZGY4XHViOGY5IFx1YzkxMSBcdWFjMDBcdWM3YTUgXHVhZTM0IFx1YWRmOFx1YjhmOVx1Yzc1OCBcdWFlMzhcdWM3NzRcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjE3OTciLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJCYWxhbmNlZCBMaW5ldXAiLCJkZXNjcmlwdGlvbiI6IjxwPkZhcm1lciBKb2huIGhhcyBkZWNpZGVkIHRvIHRha2UgYSBmYW1pbHkgcG9ydHJhaXQgb2Ygc29tZSAobWF5YmUgYWxsKSBvZiB0aGUgY293cy4gSW4gb3JkZXIgdG8gdGFrZSB0aGUgcG9ydHJhaXQsIEZKIGhhcyBhcnJhbmdlZCBhbGwgTiAoMSAmbGU7IE4gJmxlOyA1MCwwMDApIGNvd3MgaW4gYSBzdHJhaWdodCBsaW5lLiBFYWNoIGNvdyBpcyBsYWJlbGVkIHdpdGggaXRzIHggY29vcmRpbmF0ZSAocmFuZ2U6IDAuLjEsMDAwLDAwMCwwMDApIG9uIHRoZSBsaW5lIGFzIHdlbGwgYXMgaXRzIGJyZWVkICgwIG9yIDEpLjxcL3A+XHJcblxyXG48cD5PdmVyIHRoZSB5ZWFycywgRkogaGFzIGRvbmUgc29tZSBjcmF6eSB0aGluZ3MsIGFuZCB0aGlzIGFjdGl2aXR5IGlzIG5vIGV4Y2VwdGlvbi4gSGUgd2lsbCBvbmx5IHBob3RvZ3JhcGggb25lIGdyb3VwIG9mIGNvd3MsIGFuZCB0aGF0IGdyb3VwIG11c3QgYmUgJnF1b3Q7YmFsYW5jZWQmcXVvdDsuIEEgY29udGlndW91cyBncm91cCBvZiBjb3dzIGlzICZxdW90O2JhbGFuY2VkJnF1b3Q7IGlmIGl0IGNvbnRhaW5zIHRoZSBzYW1lIG51bWJlciBvZiBjb3dzIGZyb20gZWFjaCBvZiB0aGUgdHdvIGJyZWVkcy48XC9wPlxyXG5cclxuPHA+RGV0ZXJtaW5lIHRoZSB3aWRlc3QgZXhwYW5zZSBvZiBjb3dzIHRoYXQgbWlnaHQgaGF2ZSB0byBmaXQgaW4gb25lIHBob3RvZ3JhcGguIFRoZSBsZW5ndGggb2YgYSBiYWxhbmNlZCBncm91cCBpcyB0aGUgZGlmZmVyZW5jZSBpbiB4IHZhbHVlcyBiZXR3ZWVuIHRoZSBsZWZ0LW1vc3QgYW5kIHJpZ2h0LW1vc3QgY293cyBpbiB0aGUgZ3JvdXAuPFwvcD5cclxuXHJcbjxwPkF0IGxlYXN0IG9uZSBjb3cgb2YgZWFjaCBicmVlZCBhcHBlYXJzIGluIHRoZSBpbnB1dCwgYW5kIG5vIHR3byBjb3dzIHNoYXJlIHRoZSBzYW1lIHggY29vcmRpbmF0ZS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPiogTGluZSAxOiBBIHNpbmdsZSBpbnRlZ2VyOiBOPFwvcD5cclxuXHJcbjxwPiogTGluZXMgMi4uTiArIDE6IEVhY2ggbGluZSBjb250YWlucyB0d28gc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzIHRoYXQgZGVzY3JpYmUgYSBzaW5nbGUgY293IGNvbnRhaW5pbmcgcmVzcGVjdGl2ZWx5OiBhIGJyZWVkIElEIGFuZCBhbiB4IGNvb3JkaW5hdGU8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD4qIExpbmUgMTogQSBzaW5nbGUgaW50ZWdlciBzcGVjaWZ5aW5nIHRoZSBzaXplIG9mIHRoZSBsYXJnZXN0IGNvbnRpZ3VvdXMgYmFsYW5jZWQgZ3JvdXAgb2YgY293cy48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

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

  • 문제를 번역한 사람: author6
  • 빠진 조건을 찾은 사람: kks227