시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 320 165 115 57.500%

문제

베시는 스마트폰 게임을 좋아한다. 요즘은 한 게임을 재미있게 즐기고 있다. 이 게임에서는 1 이상 40 이하의 정수 N(2 ≤ N ≤ 262,144)개로 이루어진 수열이 주어진다. 연속된 두 수가 같으면 합쳐서 기존의 수보다 1 큰 수를 만들 수 있다. (예를 들어, 7이 두 개 연속되어 있으면 8로 합칠 수 있다.)

게임의 목표는 가장 큰 수를 만드는 것이다. 베시를 도와서 가능한 한 큰 수를 만들어 보자.

입력

첫 번째 줄에 N이 입력된다. 두 번째 줄부터 N줄에 걸쳐 정수가 입력된다.

출력

만들 수 있는 가장 큰 수를 출력하라.

예제 입력 1

4
1
1
1
2

예제 출력 1

3

힌트

이 예제에서는 두 번째와 세 번째 1을 합쳐서 수열 1 2 2를 만들고, 두 개의 2를 합쳐서 3을 만들 수 있다. 첫 번째와 두 번째 1을 합치는 것은 최적이 아님에 유의하라.

W3sicHJvYmxlbV9pZCI6IjEyMDA4IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiMjYyMTQ0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWJjYTBcdWMyZGNcdWIyOTQgXHVjMmE0XHViOWM4XHVkMmI4XHVkM2YwIFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWM4OGJcdWM1NDRcdWQ1NWNcdWIyZTQuIFx1YzY5NFx1Yzk5OFx1Yzc0MCBcdWQ1NWMgXHVhYzhjXHVjNzg0XHVjNzQ0IFx1YzdhY1x1YmJmOFx1Yzc4OFx1YWM4YyBcdWM5OTBcdWFlMzBcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWM3NzQgXHVhYzhjXHVjNzg0XHVjNWQwXHVjMTFjXHViMjk0IDEgXHVjNzc0XHVjMGMxIDQwIFx1Yzc3NFx1ZDU1OFx1Yzc1OCBcdWM4MTVcdWMyMTggTigyICZsZTsgTiAmbGU7IDI2MiwxNDQpXHVhYzFjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWMyMThcdWM1ZjRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM1ZjBcdWMxOGRcdWI0MWMgXHViNDUwIFx1YzIxOFx1YWMwMCBcdWFjMTlcdWM3M2NcdWJhNzQgXHVkNTY5XHVjY2QwXHVjMTFjIFx1YWUzMFx1Yzg3NFx1Yzc1OCBcdWMyMThcdWJjZjRcdWIyZTQgMSBcdWQwNzAgXHVjMjE4XHViOTdjIFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHViMmU0LiAoXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgN1x1Yzc3NCBcdWI0NTAgXHVhYzFjIFx1YzVmMFx1YzE4ZFx1YjQxOFx1YzViNCBcdWM3ODhcdWM3M2NcdWJhNzQgOFx1Yjg1YyBcdWQ1NjlcdWNlNjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4pPFwvcD5cclxuXHJcbjxwPlx1YWM4Y1x1Yzc4NFx1Yzc1OCBcdWJhYTlcdWQ0NWNcdWIyOTQgXHVhYzAwXHVjN2E1IFx1ZDA3MCBcdWMyMThcdWI5N2MgXHViOWNjXHViNGRjXHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC4gXHViY2EwXHVjMmRjXHViOTdjIFx1YjNjNFx1YzY0MFx1YzExYyBcdWFjMDBcdWIyYTVcdWQ1NWMgXHVkNTVjIFx1ZDA3MCBcdWMyMThcdWI5N2MgXHViOWNjXHViNGU0XHVjNWI0IFx1YmNmNFx1Yzc5MC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIE5cdWM3NzQgXHVjNzg1XHViODI1XHViNDFjXHViMmU0LiBcdWI0NTAgXHViYzg4XHVjOWY4IFx1YzkwNFx1YmQ4MFx1ZDEzMCBOXHVjOTA0XHVjNWQwIFx1YWM3OFx1Y2NkMCBcdWM4MTVcdWMyMThcdWFjMDAgXHVjNzg1XHViODI1XHViNDFjXHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWMwMFx1YzdhNSBcdWQwNzAgXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1Yjc3Yy48XC9wPlxyXG4iLCJoaW50IjoiPHA+XHVjNzc0IFx1YzYwOFx1YzgxY1x1YzVkMFx1YzExY1x1YjI5NCBcdWI0NTAgXHViYzg4XHVjOWY4XHVjNjQwIFx1YzEzOCBcdWJjODhcdWM5ZjggMVx1Yzc0NCBcdWQ1NjlcdWNjZDBcdWMxMWMgXHVjMjE4XHVjNWY0IDEgMiAyXHViOTdjIFx1YjljY1x1YjRlNFx1YWNlMCwgXHViNDUwIFx1YWMxY1x1Yzc1OCAyXHViOTdjIFx1ZDU2OVx1Y2NkMFx1YzExYyAzXHVjNzQ0IFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWNjYWIgXHViYzg4XHVjOWY4XHVjNjQwIFx1YjQ1MCBcdWJjODhcdWM5ZjggMVx1Yzc0NCBcdWQ1NjlcdWNlNThcdWIyOTQgXHVhYzgzXHVjNzQwIFx1Y2Q1Y1x1YzgwMVx1Yzc3NCBcdWM1NDRcdWIyZDhcdWM1ZDAgXHVjNzIwXHVjNzU4XHVkNTU4XHViNzdjLjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTIwMDgiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiIyNjIxNDQiLCJkZXNjcmlwdGlvbiI6IjxwPkJlc3NpZSBsaWtlcyBkb3dubG9hZGluZyBnYW1lcyB0byBwbGF5IG9uIGhlciBjZWxsIHBob25lLCBldmVuIHRob3VnaCBzaGUgZG9lcyBmaW5kIHRoZSBzbWFsbCB0b3VjaCBzY3JlZW4gcmF0aGVyIGN1bWJlcnNvbWUgdG8gdXNlIHdpdGggaGVyIGxhcmdlIGhvb3Zlcy48XC9wPlxyXG5cclxuPHA+U2hlIGlzIHBhcnRpY3VsYXJseSBpbnRyaWd1ZWQgYnkgdGhlIGN1cnJlbnQgZ2FtZSBzaGUgaXMgcGxheWluZy4gVGhlIGdhbWUgc3RhcnRzIHdpdGggYSBzZXF1ZW5jZSBvZiBcXChOXFwpIHBvc2l0aXZlIGludGVnZXJzIChcXCgyIFxcbGVxIE4gXFxsZXEgMjYyLDE0NFxcKSksIGVhY2ggaW4gdGhlIHJhbmdlIFxcKDEgXFxsZG90cyA0MFxcKS4gSW4gb25lIG1vdmUsIEJlc3NpZSBjYW4gdGFrZSB0d28gYWRqYWNlbnQgbnVtYmVycyB3aXRoIGVxdWFsIHZhbHVlcyBhbmQgcmVwbGFjZSB0aGVtIGEgc2luZ2xlIG51bWJlciBvZiB2YWx1ZSBvbmUgZ3JlYXRlciAoZS5nLiwgc2hlIG1pZ2h0IHJlcGxhY2UgdHdvIGFkamFjZW50IDdzIHdpdGggYW4gOCkuIFRoZSBnb2FsIGlzIHRvIG1heGltaXplIHRoZSB2YWx1ZSBvZiB0aGUgbGFyZ2VzdCBudW1iZXIgcHJlc2VudCBpbiB0aGUgc2VxdWVuY2UgYXQgdGhlIGVuZCBvZiB0aGUgZ2FtZS4gUGxlYXNlIGhlbHAgQmVzc2llIHNjb3JlIGFzIGhpZ2hseSBhcyBwb3NzaWJsZSE8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIFxcKE5cXCksIGFuZCB0aGUgbmV4dCBcXChOXFwpIGxpbmVzIGdpdmUgdGhlIHNlcXVlbmNlIG9mIFxcKE5cXCkgbnVtYmVycyBhdCB0aGUgc3RhcnQgb2YgdGhlIGdhbWUuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+UGxlYXNlIG91dHB1dCB0aGUgbGFyZ2VzdCBpbnRlZ2VyIEJlc3NpZSBjYW4gZ2VuZXJhdGUuPFwvcD5cclxuIiwiaGludCI6IjxwPkluIHRoaXMgZXhhbXBsZSBzaG93biBoZXJlLCBCZXNzaWUgZmlyc3QgbWVyZ2VzIHRoZSBzZWNvbmQgYW5kIHRoaXJkIDFzIHRvIG9idGFpbiB0aGUgc2VxdWVuY2UgMSAyIDIsIGFuZCB0aGVuIHNoZSBtZXJnZXMgdGhlIDJzIGludG8gYSAzLiBOb3RlIHRoYXQgaXQgaXMgbm90IG9wdGltYWwgdG8gam9pbiB0aGUgZmlyc3QgdHdvIDFzLjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

Olympiad > USA Computing Olympiad > 2015-2016 Season > US Open 2016 Contest > Platinum 1번

  • 문제를 번역한 사람: jh05013
  • 데이터를 추가한 사람: mhy908