시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB94235624840.857%

문제

N명의 사람이 원판 테이블에 앉아서 콜라를 마시고 있다. 그 상황에서 두 사람이 짝을 지어서 건배를 하려 한다. 그런데 이들은 건배를 할 때, 보기 좋게 하기 위하여 마시고 있는 콜라의 브랜드가 같은 경우에만 건배를 할 수 있다고 한다. 그리고 사람들이 동시에 건배를 할 때, 사람들의 팔이 서로 엇갈리는 경우에는 건배를 할 수 없다고 한다.

예를 들어 왼쪽 그림과 같은 경우는 겹치는 경우가 없어 건배를 할 수 있으나 오른쪽과 같은 경우에는 건배를 할 수 없다. 사람의 수 N과 각각의 사람이 마시는 콜라의 브랜드가 주어져 있을 때, 동시에 건배를 할 수 있는 가장 많은 쌍의 개수를 출력하시오.

입력

첫 줄에 사람의 수 (1 ≤ N ≤ 1000) 이 주어진다. 그리고 둘째 줄에 N개의 정수(1 이상 100 이하)가 공백을 사이에 두고 주어지는데 이는 각각의 사람이 마시는 콜라의 브랜드이다. (시계방향순서대로 주어진다)

출력

동시에 건배를 할 수 있는 가장 많은 쌍의 개수를 출력한다.

예제 입력 1

22
1 7 1 2 4 2 4 9 1 1 9 4 5 9 4 5 6 9 2 1 2 9

예제 출력 1

8

예제 입력 2

6
1 2 2 1 3 3

예제 출력 2

3
W3sicHJvYmxlbV9pZCI6IjE5NzAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjNzRcdWJjMzAiLCJkZXNjcmlwdGlvbiI6IjxwPk5cdWJhODVcdWM3NTggXHVjMGFjXHViNzhjXHVjNzc0IFx1YzZkMFx1ZDMxMCBcdWQxNGNcdWM3NzRcdWJlMTRcdWM1ZDAgXHVjNTQ5XHVjNTQ0XHVjMTFjIFx1Y2Y1Y1x1Yjc3Y1x1Yjk3YyBcdWI5YzhcdWMyZGNcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWFkZjggXHVjMGMxXHVkNjY5XHVjNWQwXHVjMTFjIFx1YjQ1MCBcdWMwYWNcdWI3OGNcdWM3NzQgXHVjOWRkXHVjNzQ0IFx1YzljMFx1YzViNFx1YzExYyBcdWFjNzRcdWJjMzBcdWI5N2MgXHVkNTU4XHViODI0IFx1ZDU1Y1x1YjJlNC4gXHVhZGY4XHViN2YwXHViMzcwIFx1Yzc3NFx1YjRlNFx1Yzc0MCBcdWFjNzRcdWJjMzBcdWI5N2MgXHVkNTYwIFx1YjU0YywgXHViY2Y0XHVhZTMwIFx1Yzg4Ylx1YWM4YyBcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTU4XHVjNWVjIFx1YjljOFx1YzJkY1x1YWNlMCBcdWM3ODhcdWIyOTQgXHVjZjVjXHViNzdjXHVjNzU4IFx1YmUwY1x1Yjc5Y1x1YjRkY1x1YWMwMCBcdWFjMTlcdWM3NDAgXHVhY2JkXHVjNmIwXHVjNWQwXHViOWNjIFx1YWM3NFx1YmMzMFx1Yjk3YyBcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWMwYWNcdWI3OGNcdWI0ZTRcdWM3NzQgXHViM2Q5XHVjMmRjXHVjNWQwIFx1YWM3NFx1YmMzMFx1Yjk3YyBcdWQ1NjAgXHViNTRjLCBcdWMwYWNcdWI3OGNcdWI0ZTRcdWM3NTggXHVkMzE0XHVjNzc0IFx1YzExY1x1Yjg1YyBcdWM1YzdcdWFjMDhcdWI5YWNcdWIyOTQgXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IFx1YWM3NFx1YmMzMFx1Yjk3YyBcdWQ1NjAgXHVjMjE4IFx1YzVjNlx1YjJlNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL3VwbG9hZC5hY21pY3BjLm5ldFwvOWM5MjVhZDUtNTI4MC00MzJmLThkYWQtOWFlZTY3N2VlNzY5XC8tXC9wcmV2aWV3XC9cIiBzdHlsZT1cIndpZHRoOiAyMTFweDsgaGVpZ2h0OiA5OHB4O1wiIFwvPjxcL3A+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0IFx1YzY3Y1x1Y2FiZCBcdWFkZjhcdWI5YmNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1YWNiZFx1YzZiMFx1YjI5NCBcdWFjYjlcdWNlNThcdWIyOTQgXHVhY2JkXHVjNmIwXHVhYzAwIFx1YzVjNlx1YzViNCBcdWFjNzRcdWJjMzBcdWI5N2MgXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWM3M2NcdWIwOTggXHVjNjI0XHViOTc4XHVjYWJkXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHVhYzc0XHViYzMwXHViOTdjIFx1ZDU2MCBcdWMyMTggXHVjNWM2XHViMmU0LiBcdWMwYWNcdWI3OGNcdWM3NTggXHVjMjE4IE5cdWFjZmMgXHVhYzAxXHVhYzAxXHVjNzU4IFx1YzBhY1x1Yjc4Y1x1Yzc3NCBcdWI5YzhcdWMyZGNcdWIyOTQgXHVjZjVjXHViNzdjXHVjNzU4IFx1YmUwY1x1Yjc5Y1x1YjRkY1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4MzggXHVjNzg4XHVjNzQ0IFx1YjU0YywgXHViM2Q5XHVjMmRjXHVjNWQwIFx1YWM3NFx1YmMzMFx1Yjk3YyBcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFjMDBcdWM3YTUgXHViOWNlXHVjNzQwIFx1YzMwZFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YzkwNFx1YzVkMCBcdWMwYWNcdWI3OGNcdWM3NTggXHVjMjE4ICgxICZsZTsgTiAmbGU7IDEwMDApIFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwIE5cdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4KDEgXHVjNzc0XHVjMGMxIDEwMCBcdWM3NzRcdWQ1NTgpXHVhYzAwIFx1YWNmNVx1YmMzMVx1Yzc0NCBcdWMwYWNcdWM3NzRcdWM1ZDAgXHViNDUwXHVhY2UwIFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NFx1YjM3MCBcdWM3NzRcdWIyOTQgXHVhYzAxXHVhYzAxXHVjNzU4IFx1YzBhY1x1Yjc4Y1x1Yzc3NCBcdWI5YzhcdWMyZGNcdWIyOTQgXHVjZjVjXHViNzdjXHVjNzU4IFx1YmUwY1x1Yjc5Y1x1YjRkY1x1Yzc3NFx1YjJlNC4gKFx1YzJkY1x1YWNjNFx1YmMyOVx1ZDVhNVx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQpPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHViM2Q5XHVjMmRjXHVjNWQwIFx1YWM3NFx1YmMzMFx1Yjk3YyBcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFjMDBcdWM3YTUgXHViOWNlXHVjNzQwIFx1YzMwZFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjE5NzAiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJUaGUgQmF2YXJpYW4gQmVlciBQYXJ0eSIsImRlc2NyaXB0aW9uIjoiPHA+VGhlIHByb2Zlc3NvcnMgb2YgdGhlIEJheWVyaXNjaGUgTWF0aGVtYXRpa2VyIFZlcmVpbiBoYXZlIHRoZWlyIGFubnVhbCBwYXJ0eSBpbiB0aGUgbG9jYWwgQmllcmdhcnRlbi4gVGhleSBhcmUgc2l0dGluZyBhdCBhIHJvdW5kIHRhYmxlIGVhY2ggd2l0aCBoaXMgb3duIHBpbnQgb2YgYmVlci4gQXMgYSBjZXJlbW9ueSBlYWNoIHByb2Zlc3NvciByYWlzZXMgaGlzIHBpbnQgYW5kIHRvYXN0cyBvbmUgb2YgdGhlIG90aGVyIGd1ZXN0cyBpbiBzdWNoIGEgd2F5IHRoYXQgbm8gYXJtcyBjcm9zcy4mbmJzcDs8XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC85YzkyNWFkNS01MjgwLTQzMmYtOGRhZC05YWVlNjc3ZWU3NjlcLy1cL3ByZXZpZXdcL1wiIHN0eWxlPVwid2lkdGg6IDIxMXB4OyBoZWlnaHQ6IDk4cHg7XCIgXC8+PFwvcD5cclxuXHJcbjxwPkZpZ3VyZSAyOiBUb2FzdGluZyBhY3Jvc3MgYSB0YWJsZSB3aXRoIGVpZ2h0IHBlcnNvbnM6bm8gYXJtcyBjcm9zc2luZyhsZWZ0KSwgYXJtcyBjcm9zc2luZyhyaWdodCkmbmJzcDs8XC9wPlxyXG5cclxuPHA+V2Uga25vdyB0aGF0IHRoZSBwcm9mZXNzb3JzIGxpa2UgdG8gdG9hc3Qgd2l0aCBzb21lb25lIHRoYXQgaXMgZHJpbmtpbmcgdGhlIHNhbWUgYnJhbmQgb2YgYmVlciwgYW5kIHdlIGxpa2UgdG8gbWF4aW1pemUgdGhlIG51bWJlciBvZiBwYWlycyBvZiBwcm9mZXNzb3JzIHRvYXN0aW5nIHdpdGggdGhlIHNhbWUgYnJhbmQgLCBhZ2FpbiB3aXRob3V0IGNyb3NzaW5nIGFybXMuIFdyaXRlIGFuIGFsZ29yaXRobSB0byBkbyB0aGlzLCBrZWVwaW5nIGluIG1pbmQgdGhhdCBldmVyeSBwcm9mZXNzb3Igc2hvdWxkIHRha2UgcGFydCBpbiB0aGUgdG9hc3RpbmcuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZnJpc3QgbGluZSBvZiB0aGUgaW5wdXQgY29udGFpbnMgYSBzaW5nbGUgbnVtYmVyOiB0aGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMgdG8gZm9sbG93LiBFYWNoIHRlc3QgY2FzZSBoYXMgdGhlIGZvbGxvd2luZyBmb3JtYXQ6Jm5ic3A7PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+T25lIGxpbmUgd2l0aCBhbiBldmVuIG51bWJlciBwLCBzYXRpc2Z5aW5nIDIgJmxlOyBwICZsZTsgMTAwMDogdGhlIG51bWJlciBvZiBwYXJ0aWNpcGFudHMmbmJzcDs8XC9saT5cclxuXHQ8bGk+T25lIGxpbmUgd2l0aCBwIGludGVnZXJzIChzZXBhcmF0ZWQgYnkgc2luZ2xlIHNwYWNlcykgaW5kaWNhdGluZyB0aGUgYmVlciBicmFuZHMgZnJvIHRoZSBjb25zZWN1dGl2ZSBwcm9mZXNzb3JzKCBpbiBjbG9ja3dpc2Ugb3JkZXIsIHN0YXJ0aW5nIGF0IGFuIGFyYml0cmFyeSBwb3NpdGlvbikuIEVhY2ggdmFsdWUgaXMgYmV0d2VlbiAxIGFuZCAxMDAgKGJvdWRhcmllcyBpbmNsdWRlZCkuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZXZlcnkgdGVzdCBjYXNlIGluIHRoZSBpbnB1dCwgdGhlIG91dHB1dCBzaG91bGQgY29udGFpbiBhIHNpbmdsZSBudW1iZXIgb24gYSBzaW5nbGUgbGluZTogdGhlIG1heGltdW0gbnVtYmVyIG9mIG5vbi1pbnRlcnNlY3RpbmcgdG9hc3RzIG9mIHRoZSBzYW1lIGJlZXIgYnJhbmQgZm9yIHRoaXMgdGVzdCBjYXNlLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

ICPC > Regionals > Europe > Northwestern European Regional Contest > Benelux Algorithm Programming Contest > BAPC 2006 E번

  • 잘못된 조건을 찾은 사람: Apple_Cplus
  • 데이터를 추가한 사람: cgiosy