시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 416 139 117 50.215%

문제

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+XHJcblxyXG48cD5cdWFkZjhcdWIxNDBcdWIyOTQgXHVkMmI5XHVkNzg4IFx1YzY5NFx1Yzk5OCBcdWQ1NThcdWFjZTBcdWM3ODhcdWIyOTQgXHVhYzhjXHVjNzg0XHVjNWQwIFx1ZDc2NVx1YmJmOFx1Yjk3YyBcdWIyOTBcdWIwN2NcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWM3NzQgXHVhYzhjXHVjNzg0XHVjNzQwIE5cdWFjMWNcdWM3NTggXHVjNTkxXHVjMjE4XHViNGU0KDIgJmxlOyBOICZsZTsgMjQ4KVx1Yjg1YyBcdWMyZGNcdWM3OTFcdWI0MThcdWJhNzAsIFx1YWMwMSBcdWMyMThcdWIyOTQgMVx1YzVkMFx1YzExYyA0MCBcdWMwYWNcdWM3NzRcdWM3NzRcdWIyZTQuIFx1YWMwMSBcdWMyMThcdWM1ZDBcdWMxMWMgQmVzc2llXHViMjk0IFx1YWMxOVx1Yzc0MCBcdWFjMTJcdWM3NDQgXHVhYzAwXHVjOWM0IFx1YjQ1MFx1YWMxY1x1Yzc1OCBcdWM3NzhcdWM4MTFcdWQ1NWMgXHVjMjE4XHViOTdjIFx1YWRmOFx1YmNmNFx1YjJlNCAxIFx1ZDA3MCBcdWMyMTggXHVkNTVjXHVhYzFjXHViODVjIFx1YmMxNFx1YWZjMCBcdWMyMTggXHVjNzg4XHViMmU0LiAoXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgXHVhZGY4XHViMTQwXHViMjk0IFx1YjQ1MCBcdWFjMWNcdWM3NTggXHVjNzc4XHVjODExXHVkNTVjIDdcdWM3NDQgOFx1Yjg1YyBcdWJjMTRcdWFmYzAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4pIFx1YmFhOVx1ZDQ1Y1x1YjI5NCBcdWMyMThcdWM1ZjRcdWM1ZDBcdWMxMWMgXHViMzU0XHVjNzc0XHVjMGMxIFx1ZDU2OVx1Y2U2MCBcdWMyMThcdWFjMDAgXHViMGE4XHVjNTQ0XHVjNzg4XHVjOWMwIFx1YzU0YVx1Yzc0NCBcdWI1NGMsIFx1Yzk4OSBcdWFjOGNcdWM3ODRcdWM3NzQgXHViMDVkXHViMGFjXHVjNzQ0IFx1YjU0YyBcdWMyMThcdWM1ZjRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YWMwMFx1YzdhNSBcdWQwNzAgXHVjMjE4XHViOTdjIFx1Y2Q1Y1x1YjMwMFx1ZDY1NCBcdWQ1NThcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LiBCZXNzaWVcdWFjMDAgXHVhYzAwXHViMmE1XHVkNTVjIFx1YWMwMFx1YzdhNSBcdWIxOTJcdWM3NDAgXHVjODEwXHVjMjE4XHViOTdjIFx1YzViYlx1Yzc0NCBcdWMyMTggXHVjNzg4XHViM2M0XHViODVkIFx1YjNjNFx1YzY0MFx1YzhmY1x1YzViNFx1Yjc3YyE8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgTlx1Yzc0NCBcdWM3ODVcdWI4MjVcdWJjMWJcdWIyOTRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjJcdWJjODhcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwIE5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWM4Y1x1Yzc4NFx1Yzc1OCBcdWMyZGNcdWM3OTFcdWM1ZDBcdWMxMWMgXHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0IE5cdWFjMWNcdWM3NTggXHVjMjJiXHVjNzkwXHViOTdjIFx1Yzc4NVx1YjgyNVx1YmMxYlx1YjI5NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5CZXNzaWVcdWFjMDAgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhYzAwXHVjN2E1IFx1ZDA3MCBcdWM4MTVcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTc0XHViNzdjLjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cdWM3NzQgXHVjNjA4XHVjNWQwXHVjMTFjLCBCZXNzaWVcdWIyOTQgXHViNDUwIFx1YmM4OFx1YzlmOFx1YzY0MCBcdWMxMzggXHViYzg4XHVjOWY4XHVjNWQwIFx1Yzc4OFx1YjI5NCAxXHVjNzQ0IDJcdWI4NWMgXHVkNTY5XHVjZTVjXHViMmU0LiAoMSAyIDIpPFwvcD5cclxuXHJcbjxwPlx1YjQ1MCBcdWJjODhcdWM5ZjhcdWM2NDAgXHVjMTM4IFx1YmM4OFx1YzlmOFx1YzVkMCBcdWM3ODhcdWIyOTQgMlx1Yjk3YyAzXHVjNzNjXHViODVjIFx1ZDU2OVx1Y2U1Y1x1YjJlNC4gKDEgMyk8XC9wPlxyXG5cclxuPHA+XHVjY2FiIFx1YmM4OFx1YzlmOFx1YzY0MCBcdWI0NTAgXHViYzg4XHVjOWY4IDFcdWM3NDQgXHVkNTY5XHVjZTU4XHViMjk0IFx1YWM4M1x1Yzc0MCBcdWNkNWNcdWM4MDFcdWQ1NzRcdWFjMDAgXHVjNTQ0XHViMmQ4XHVjNzQ0IFx1YzhmY1x1Yzc1OFx1ZDU3NFx1Yjc3Yy48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjEyMDEzIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiMjQ4IiwiZGVzY3JpcHRpb24iOiI8cD5CZXNzaWUgbGlrZXMgZG93bmxvYWRpbmcgZ2FtZXMgdG8gcGxheSBvbiBoZXIgY2VsbCBwaG9uZSwgZXZlbiB0aG91Z2ggc2hlIGRvZXMgZmluZCB0aGUgc21hbGwgdG91Y2ggc2NyZWVuIHJhdGhlciBjdW1iZXJzb21lIHRvIHVzZSB3aXRoIGhlciBsYXJnZSBob292ZXMuPFwvcD5cclxuXHJcbjxwPlNoZSBpcyBwYXJ0aWN1bGFybHkgaW50cmlndWVkIGJ5IHRoZSBjdXJyZW50IGdhbWUgc2hlIGlzIHBsYXlpbmcuIFRoZSBnYW1lIHN0YXJ0cyB3aXRoIGEgc2VxdWVuY2Ugb2YgXFwoTlxcKSBwb3NpdGl2ZSBpbnRlZ2VycyAoXFwoMiBcXGxlcSBOIFxcbGVxIDI0OFxcKSksIGVhY2ggaW4gdGhlIHJhbmdlIFxcKDEgXFxsZG90cyA0MFxcKS4gSW4gb25lIG1vdmUsIEJlc3NpZSBjYW4gdGFrZSB0d28gYWRqYWNlbnQgbnVtYmVycyB3aXRoIGVxdWFsIHZhbHVlcyBhbmQgcmVwbGFjZSB0aGVtIGEgc2luZ2xlIG51bWJlciBvZiB2YWx1ZSBvbmUgZ3JlYXRlciAoZS5nLiwgc2hlIG1pZ2h0IHJlcGxhY2UgdHdvIGFkamFjZW50IDdzIHdpdGggYW4gOCkuIFRoZSBnb2FsIGlzIHRvIG1heGltaXplIHRoZSB2YWx1ZSBvZiB0aGUgbGFyZ2VzdCBudW1iZXIgcHJlc2VudCBpbiB0aGUgc2VxdWVuY2UgYXQgdGhlIGVuZCBvZiB0aGUgZ2FtZS4gUGxlYXNlIGhlbHAgQmVzc2llIHNjb3JlIGFzIGhpZ2hseSBhcyBwb3NzaWJsZSE8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIFxcKE5cXCksIGFuZCB0aGUgbmV4dCBcXChOXFwpIGxpbmVzIGdpdmUgdGhlIHNlcXVlbmNlIG9mIFxcKE5cXCkgbnVtYmVycyBhdCB0aGUgc3RhcnQgb2YgdGhlIGdhbWUuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+UGxlYXNlIG91dHB1dCB0aGUgbGFyZ2VzdCBpbnRlZ2VyIEJlc3NpZSBjYW4gZ2VuZXJhdGUuPFwvcD5cclxuXHJcbiIsImhpbnQiOiI8cD5JbiB0aGlzIGV4YW1wbGUgc2hvd24gaGVyZSwgQmVzc2llIGZpcnN0IG1lcmdlcyB0aGUgc2Vjb25kIGFuZCB0aGlyZCAxcyB0byBvYnRhaW4gdGhlIHNlcXVlbmNlIDEgMiAyLCBhbmQgdGhlbiBzaGUgbWVyZ2VzIHRoZSAycyBpbnRvIGEgMy4gTm90ZSB0aGF0IGl0IGlzIG5vdCBvcHRpbWFsIHRvIGpvaW4gdGhlIGZpcnN0IHR3byAxcy48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

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