시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 198 96 71 47.973%

문제

Bessie는 큰 손으로 작은 터치스크린을 다루는 것이 불편함에도 불구하고 휴대폰으로 게임을 하는 것을 좋아한다.

그녀는 특히 요즘 하고있는 게임에 흥미를 느끼고 있다. 이 게임은 N개의 양수들(2<=N<=248)로 시작되며, 각 수는 1에서 40 사이이다. 각 수에서 Bessie는 같은 값을 가진 두개의 인접한 수를 그보다 1 큰 수 한개로 바꿀 수 있다. (예를 들어, 그녀는 두 개의 인접한 7을 8로 바꿀 수 있다.) 목표는 수열에서 더이상 합칠 수가 남아있지 않을 때, 즉 게임이 끝났을 때 수열에 있는 가장 큰 수를 최대화 하는 것이다. Bessie가 가능한 가장 높은 점수를 얻을 수 있도록 도와주어라!

입력

첫째 줄에는 N을 입력받는다.

2번째 줄부터 N개의 줄에는 게임의 시작에서 주어지는 N개의 숫자를 입력받는다.

출력

Bessie가 만들 수 있는 가장 큰 정수를 출력해라.

예제 입력 1

4
1
1
1
2

예제 출력 1

3

힌트

이 예에서, Bessie는 두번째와 세번째에 있는 1을 2로 합친다. (1 2 2)

두번째와 세번째에 있는 2를 3으로 합친다. (1 3)

첫번째와 두번째 1을 합치는 것은 최적해가 아님을 주의해라.

W3sicHJvYmxlbV9pZCI6IjEyMDEzIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiMjQ4IFx1YWM4Y1x1Yzc4NCIsImRlc2NyaXB0aW9uIjoiPHA+QmVzc2llXHViMjk0IFx1ZDA3MCBcdWMxOTBcdWM3M2NcdWI4NWMgXHVjNzkxXHVjNzQwIFx1ZDEzMFx1Y2U1OFx1YzJhNFx1ZDA2Y1x1YjliMFx1Yzc0NCBcdWIyZTRcdWI4ZThcdWIyOTQmbmJzcDtcdWFjODNcdWM3NzQgXHViZDg4XHVkM2I4XHVkNTY4XHVjNWQwXHViM2M0IFx1YmQ4OFx1YWQ2Y1x1ZDU1OFx1YWNlMCBcdWQ3MzRcdWIzMDBcdWQzZjBcdWM3M2NcdWI4NWMgXHVhYzhjXHVjNzg0XHVjNzQ0IFx1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NDQgXHVjODhiXHVjNTQ0XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFkZjhcdWIxNDBcdWIyOTQgXHVkMmI5XHVkNzg4IFx1YzY5NFx1Yzk5OCBcdWQ1NThcdWFjZTBcdWM3ODhcdWIyOTQgXHVhYzhjXHVjNzg0XHVjNWQwIFx1ZDc2NVx1YmJmOFx1Yjk3YyBcdWIyOTBcdWIwN2NcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWM3NzQgXHVhYzhjXHVjNzg0XHVjNzQwIE5cdWFjMWNcdWM3NTggXHVjNTkxXHVjMjE4XHViNGU0KDImbHQ7PU4mbHQ7PTI0OClcdWI4NWMgXHVjMmRjXHVjNzkxXHViNDE4XHViYTcwLCBcdWFjMDEgXHVjMjE4XHViMjk0IDFcdWM1ZDBcdWMxMWMgNDAgXHVjMGFjXHVjNzc0XHVjNzc0XHViMmU0LiBcdWFjMDEgXHVjMjE4XHVjNWQwXHVjMTFjIEJlc3NpZVx1YjI5NCBcdWFjMTlcdWM3NDAgXHVhYzEyXHVjNzQ0IFx1YWMwMFx1YzljNCBcdWI0NTBcdWFjMWNcdWM3NTggXHVjNzc4XHVjODExXHVkNTVjIFx1YzIxOFx1Yjk3YyBcdWFkZjhcdWJjZjRcdWIyZTQgMSBcdWQwNzAgXHVjMjE4IFx1ZDU1Y1x1YWMxY1x1Yjg1YyBcdWJjMTRcdWFmYzAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gKFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIFx1YWRmOFx1YjE0MFx1YjI5NCBcdWI0NTAgXHVhYzFjXHVjNzU4IFx1Yzc3OFx1YzgxMVx1ZDU1YyA3XHVjNzQ0IDhcdWI4NWMgXHViYzE0XHVhZmMwIFx1YzIxOCBcdWM3ODhcdWIyZTQuKSBcdWJhYTlcdWQ0NWNcdWIyOTQgXHVjMjE4XHVjNWY0XHVjNWQwXHVjMTFjIFx1YjM1NFx1Yzc3NFx1YzBjMSBcdWQ1NjlcdWNlNjAgXHVjMjE4XHVhYzAwIFx1YjBhOFx1YzU0NFx1Yzc4OFx1YzljMCBcdWM1NGFcdWM3NDQgXHViNTRjLCBcdWM5ODkgXHVhYzhjXHVjNzg0XHVjNzc0IFx1YjA1ZFx1YjBhY1x1Yzc0NCBcdWI1NGMgXHVjMjE4XHVjNWY0XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWFjMDBcdWM3YTUgXHVkMDcwIFx1YzIxOFx1Yjk3YyBcdWNkNWNcdWIzMDBcdWQ2NTQgXHVkNTU4XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC4gQmVzc2llXHVhYzAwIFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWFjMDBcdWM3YTUgXHViMTkyXHVjNzQwIFx1YzgxMFx1YzIxOFx1Yjk3YyBcdWM1YmJcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjNjNFx1Yjg1ZCBcdWIzYzRcdWM2NDBcdWM4ZmNcdWM1YjRcdWI3N2MhPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IE5cdWM3NDQgXHVjNzg1XHViODI1XHViYzFiXHViMjk0XHViMmU0LjxcL3A+XHJcblxyXG48cD4yXHViYzg4XHVjOWY4IFx1YzkwNFx1YmQ4MFx1ZDEzMCBOXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjOGNcdWM3ODRcdWM3NTggXHVjMmRjXHVjNzkxXHVjNWQwXHVjMTFjIFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NCBOXHVhYzFjXHVjNzU4IFx1YzIyYlx1Yzc5MFx1Yjk3YyBcdWM3ODVcdWI4MjVcdWJjMWJcdWIyOTRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+QmVzc2llXHVhYzAwIFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWMwMFx1YzdhNSBcdWQwNzAgXHVjODE1XHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU3NFx1Yjc3Yy48XC9wPlxyXG4iLCJoaW50IjoiPHA+XHVjNzc0IFx1YzYwOFx1YzVkMFx1YzExYywgQmVzc2llXHViMjk0IFx1YjQ1MFx1YmM4OFx1YzlmOFx1YzY0MCBcdWMxMzhcdWJjODhcdWM5ZjhcdWM1ZDAgXHVjNzg4XHViMjk0IDFcdWM3NDQgMlx1Yjg1YyBcdWQ1NjlcdWNlNWNcdWIyZTQuICgxIDIgMik8XC9wPlxyXG5cclxuPHA+XHViNDUwXHViYzg4XHVjOWY4XHVjNjQwIFx1YzEzOFx1YmM4OFx1YzlmOFx1YzVkMCBcdWM3ODhcdWIyOTQgMlx1Yjk3YyAzXHVjNzNjXHViODVjIFx1ZDU2OVx1Y2U1Y1x1YjJlNC4gKDEgMyk8XC9wPlxyXG5cclxuPHA+XHVjY2FiXHViYzg4XHVjOWY4XHVjNjQwIFx1YjQ1MFx1YmM4OFx1YzlmOCAxXHVjNzQ0IFx1ZDU2OVx1Y2U1OFx1YjI5NCBcdWFjODNcdWM3NDAgXHVjZDVjXHVjODAxXHVkNTc0XHVhYzAwIFx1YzU0NFx1YjJkOFx1Yzc0NCBcdWM4ZmNcdWM3NThcdWQ1NzRcdWI3N2MuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxMjAxMyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IjI0OCIsImRlc2NyaXB0aW9uIjoiPHA+QmVzc2llIGxpa2VzIGRvd25sb2FkaW5nIGdhbWVzIHRvIHBsYXkgb24gaGVyIGNlbGwgcGhvbmUsIGV2ZW4gdGhvdWdoIHNoZSBkb2VzIGZpbmQgdGhlIHNtYWxsIHRvdWNoIHNjcmVlbiByYXRoZXIgY3VtYmVyc29tZSB0byB1c2Ugd2l0aCBoZXIgbGFyZ2UgaG9vdmVzLjxcL3A+XHJcblxyXG48cD5TaGUgaXMgcGFydGljdWxhcmx5IGludHJpZ3VlZCBieSB0aGUgY3VycmVudCBnYW1lIHNoZSBpcyBwbGF5aW5nLiBUaGUgZ2FtZSBzdGFydHMgd2l0aCBhIHNlcXVlbmNlIG9mIFxcKE5cXCkgcG9zaXRpdmUgaW50ZWdlcnMgKFxcKDIgXFxsZXEgTiBcXGxlcSAyNDhcXCkpLCBlYWNoIGluIHRoZSByYW5nZSBcXCgxIFxcbGRvdHMgNDBcXCkuIEluIG9uZSBtb3ZlLCBCZXNzaWUgY2FuIHRha2UgdHdvIGFkamFjZW50IG51bWJlcnMgd2l0aCBlcXVhbCB2YWx1ZXMgYW5kIHJlcGxhY2UgdGhlbSBhIHNpbmdsZSBudW1iZXIgb2YgdmFsdWUgb25lIGdyZWF0ZXIgKGUuZy4sIHNoZSBtaWdodCByZXBsYWNlIHR3byBhZGphY2VudCA3cyB3aXRoIGFuIDgpLiBUaGUgZ29hbCBpcyB0byBtYXhpbWl6ZSB0aGUgdmFsdWUgb2YgdGhlIGxhcmdlc3QgbnVtYmVyIHByZXNlbnQgaW4gdGhlIHNlcXVlbmNlIGF0IHRoZSBlbmQgb2YgdGhlIGdhbWUuIFBsZWFzZSBoZWxwIEJlc3NpZSBzY29yZSBhcyBoaWdobHkgYXMgcG9zc2libGUhPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyBcXChOXFwpLCBhbmQgdGhlIG5leHQgXFwoTlxcKSBsaW5lcyBnaXZlIHRoZSBzZXF1ZW5jZSBvZiBcXChOXFwpIG51bWJlcnMgYXQgdGhlIHN0YXJ0IG9mIHRoZSBnYW1lLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlBsZWFzZSBvdXRwdXQgdGhlIGxhcmdlc3QgaW50ZWdlciBCZXNzaWUgY2FuIGdlbmVyYXRlLjxcL3A+XHJcblxyXG4iLCJoaW50IjoiPHA+SW4gdGhpcyBleGFtcGxlIHNob3duIGhlcmUsIEJlc3NpZSBmaXJzdCBtZXJnZXMgdGhlIHNlY29uZCBhbmQgdGhpcmQgMXMgdG8gb2J0YWluIHRoZSBzZXF1ZW5jZSAxIDIgMiwgYW5kIHRoZW4gc2hlIG1lcmdlcyB0aGUgMnMgaW50byBhIDMuIE5vdGUgdGhhdCBpdCBpcyBub3Qgb3B0aW1hbCB0byBqb2luIHRoZSBmaXJzdCB0d28gMXMuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Olympiad > USA Computing Olympiad > 2015-2016 Season > US Open 2016 Contest > Gold 3번