시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 110 44 35 63.636%

문제

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
W3sicHJvYmxlbV9pZCI6IjE5NzAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjNzRcdWJjMzAiLCJkZXNjcmlwdGlvbiI6IjxwPk5cdWJhODVcdWM3NTggXHVjMGFjXHViNzhjXHVjNzc0IFx1YzZkMFx1ZDMxMCBcdWQxNGNcdWM3NzRcdWJlMTRcdWM1ZDAgXHVjNTQ5XHVjNTQ0XHVjMTFjIFx1Y2Y1Y1x1Yjc3Y1x1Yjk3YyBcdWI5YzhcdWMyZGNcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWFkZjggXHVjMGMxXHVkNjY5XHVjNWQwXHVjMTFjIFx1YjQ1MCBcdWMwYWNcdWI3OGNcdWM3NzQgXHVjOWRkXHVjNzQ0IFx1YzljMFx1YzViNFx1YzExYyBcdWFjNzRcdWJjMzBcdWI5N2MgXHVkNTU4XHViODI0IFx1ZDU1Y1x1YjJlNC4gXHVhZGY4XHViN2YwXHViMzcwIFx1Yzc3NFx1YjRlNFx1Yzc0MCBcdWFjNzRcdWJjMzBcdWI5N2MgXHVkNTYwIFx1YjU0YywgXHViY2Y0XHVhZTMwIFx1Yzg4Ylx1YWM4YyBcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTU4XHVjNWVjIFx1YjljOFx1YzJkY1x1YWNlMCBcdWM3ODhcdWIyOTQgXHVjZjVjXHViNzdjXHVjNzU4IFx1YmUwY1x1Yjc5Y1x1YjRkY1x1YWMwMCBcdWFjMTlcdWM3NDAgXHVhY2JkXHVjNmIwXHVjNWQwXHViOWNjIFx1YWM3NFx1YmMzMFx1Yjk3YyBcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWMwYWNcdWI3OGNcdWI0ZTRcdWM3NzQgXHViM2Q5XHVjMmRjXHVjNWQwIFx1YWM3NFx1YmMzMFx1Yjk3YyBcdWQ1NjAgXHViNTRjLCBcdWMwYWNcdWI3OGNcdWI0ZTRcdWM3NTggXHVkMzE0XHVjNzc0IFx1YzExY1x1Yjg1YyBcdWM1YzdcdWFjMDhcdWI5YWNcdWIyOTQgXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IFx1YWM3NFx1YmMzMFx1Yjk3YyBcdWQ1NjAgXHVjMjE4IFx1YzVjNlx1YjJlNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuPHA+PGltZyB3aWR0aD1cIjMyNlwiIGhlaWdodD1cIjE0NlwiIGFsdD1cIlwiIHNyYz1cIlwvSnVkZ2VPbmxpbmVcL3VwbG9hZFwvMjAxMDA3XC9nYi5wbmdcIiBcLz48XC9wPlxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0IFx1YzY3Y1x1Y2FiZCBcdWFkZjhcdWI5YmNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1YWNiZFx1YzZiMFx1YjI5NCBcdWFjYjlcdWNlNThcdWIyOTQgXHVhY2JkXHVjNmIwXHVhYzAwIFx1YzVjNlx1YzViNCBcdWFjNzRcdWJjMzBcdWI5N2MgXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWM3M2NcdWIwOTggXHVjNjI0XHViOTc4XHVjYWJkXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHVhYzc0XHViYzMwXHViOTdjIFx1ZDU2MCBcdWMyMTggXHVjNWM2XHViMmU0LiBcdWMwYWNcdWI3OGNcdWM3NTggXHVjMjE4IE5cdWFjZmMgXHVhYzAxXHVhYzAxXHVjNzU4IFx1YzBhY1x1Yjc4Y1x1Yzc3NCBcdWI5YzhcdWMyZGNcdWIyOTQgXHVjZjVjXHViNzdjXHVjNzU4IFx1YmUwY1x1Yjc5Y1x1YjRkY1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4MzggXHVjNzg4XHVjNzQ0IFx1YjU0YywgXHViM2Q5XHVjMmRjXHVjNWQwIFx1YWM3NFx1YmMzMFx1Yjk3YyBcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFjMDBcdWM3YTUgXHViOWNlXHVjNzQwIFx1YzMwZFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+IiwiaW5wdXQiOiI8cD5cdWNjYWIgXHVjOTA0XHVjNWQwIFx1YzBhY1x1Yjc4Y1x1Yzc1OCBcdWMyMTggKDEmbHQ7PU4mbHQ7PTEwMDApIFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwIE5cdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4KDEgXHVjNzc0XHVjMGMxIDEwMCBcdWM3NzRcdWQ1NTgpXHVhYzAwIFx1YWNmNVx1YmMzMVx1Yzc0NCBcdWMwYWNcdWM3NzRcdWM1ZDAgXHViNDUwXHVhY2UwIFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NFx1YjM3MCBcdWM3NzRcdWIyOTQgXHVhYzAxXHVhYzAxXHVjNzU4IFx1YzBhY1x1Yjc4Y1x1Yzc3NCBcdWI5YzhcdWMyZGNcdWIyOTQgXHVjZjVjXHViNzdjXHVjNzU4IFx1YmUwY1x1Yjc5Y1x1YjRkY1x1Yzc3NFx1YjJlNC4gKFx1YzJkY1x1YWNjNFx1YmMyOVx1ZDVhNVx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQpPFwvcD4iLCJvdXRwdXQiOiI8cD5cdWIzZDlcdWMyZGNcdWM1ZDAgXHVhYzc0XHViYzMwXHViOTdjIFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWMwMFx1YzdhNSBcdWI5Y2VcdWM3NDAgXHVjMzBkXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxOTcwIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiVGhlIEJhdmFyaWFuIEJlZXIgUGFydHkiLCJkZXNjcmlwdGlvbiI6IjxwPlRoZSBwcm9mZXNzb3JzIG9mIHRoZSBCYXllcmlzY2hlIE1hdGhlbWF0aWtlciBWZXJlaW4gaGF2ZSB0aGVpciBhbm51YWwgcGFydHkgaW4gdGhlIGxvY2FsIEJpZXJnYXJ0ZW4uIFRoZXkgYXJlIHNpdHRpbmcgYXQgYSByb3VuZCB0YWJsZSBlYWNoIHdpdGggaGlzIG93biBwaW50IG9mIGJlZXIuIEFzIGEgY2VyZW1vbnkgZWFjaCBwcm9mZXNzb3IgcmFpc2VzIGhpcyBwaW50IGFuZCB0b2FzdHMgb25lIG9mIHRoZSBvdGhlciBndWVzdHMgaW4gc3VjaCBhIHdheSB0aGF0IG5vIGFybXMgY3Jvc3MuJm5ic3A7PFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvYmVlci5wbmdcIiBzdHlsZT1cImhlaWdodDoxMDdweDsgd2lkdGg6MjQycHhcIiBcLz48XC9wPlxyXG5cclxuPHA+RmlndXJlIDI6IFRvYXN0aW5nIGFjcm9zcyBhIHRhYmxlIHdpdGggZWlnaHQgcGVyc29uczpubyBhcm1zIGNyb3NzaW5nKGxlZnQpLCBhcm1zIGNyb3NzaW5nKHJpZ2h0KSZuYnNwOzxcL3A+XHJcblxyXG48cD5XZSBrbm93IHRoYXQgdGhlIHByb2Zlc3NvcnMgbGlrZSB0byB0b2FzdCB3aXRoIHNvbWVvbmUgdGhhdCBpcyBkcmlua2luZyB0aGUgc2FtZSBicmFuZCBvZiBiZWVyLCBhbmQgd2UgbGlrZSB0byBtYXhpbWl6ZSB0aGUgbnVtYmVyIG9mIHBhaXJzIG9mIHByb2Zlc3NvcnMgdG9hc3Rpbmcgd2l0aCB0aGUgc2FtZSBicmFuZCAsIGFnYWluIHdpdGhvdXQgY3Jvc3NpbmcgYXJtcy4gV3JpdGUgYW4gYWxnb3JpdGhtIHRvIGRvIHRoaXMsIGtlZXBpbmcgaW4gbWluZCB0aGF0IGV2ZXJ5IHByb2Zlc3NvciBzaG91bGQgdGFrZSBwYXJ0IGluIHRoZSB0b2FzdGluZy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmcmlzdCBsaW5lIG9mIHRoZSBpbnB1dCBjb250YWlucyBhIHNpbmdsZSBudW1iZXI6IHRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcyB0byBmb2xsb3cuIEVhY2ggdGVzdCBjYXNlIGhhcyB0aGUgZm9sbG93aW5nIGZvcm1hdDombmJzcDs8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5PbmUgbGluZSB3aXRoIGFuIGV2ZW4gbnVtYmVyIHAsIHNhdGlzZnlpbmcgMiAmbGU7IHAgJmxlOyAxMDAwOiB0aGUgbnVtYmVyIG9mIHBhcnRpY2lwYW50cyZuYnNwOzxcL2xpPlxyXG5cdDxsaT5PbmUgbGluZSB3aXRoIHAgaW50ZWdlcnMgKHNlcGFyYXRlZCBieSBzaW5nbGUgc3BhY2VzKSBpbmRpY2F0aW5nIHRoZSBiZWVyIGJyYW5kcyBmcm8gdGhlIGNvbnNlY3V0aXZlIHByb2Zlc3NvcnMoIGluIGNsb2Nrd2lzZSBvcmRlciwgc3RhcnRpbmcgYXQgYW4gYXJiaXRyYXJ5IHBvc2l0aW9uKS4gRWFjaCB2YWx1ZSBpcyBiZXR3ZWVuIDEgYW5kIDEwMCAoYm91ZGFyaWVzIGluY2x1ZGVkKS48XC9saT5cclxuPFwvdWw+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBldmVyeSB0ZXN0IGNhc2UgaW4gdGhlIGlucHV0LCB0aGUgb3V0cHV0IHNob3VsZCBjb250YWluIGEgc2luZ2xlIG51bWJlciBvbiBhIHNpbmdsZSBsaW5lOiB0aGUgbWF4aW11bSBudW1iZXIgb2Ygbm9uLWludGVyc2VjdGluZyB0b2FzdHMgb2YgdGhlIHNhbWUgYmVlciBicmFuZCBmb3IgdGhpcyB0ZXN0IGNhc2UuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==