시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 189 95 64 53.782%

문제

베시는 스마트 폰 게임을 좋아한다. 현재 재미있게 하는 게임은 시작 할 때, 1~40 범위를 갖는 N(2≤N≤262,144)개의 정수가 주어지는데 연속된 두 수가 같으면 하나로 합칠 수 있는데 합칠 경우 기존 값보다 1이 큰 수를 만들 수 있다. (예를 들어, 7이 두 개 연속되어 있으면 8로 합칠 수 있다)
 
게임의 목표는 가장 큰 수를 만드는 것이다. 베시를 도와서 가능한 가장 큰 수를 만들 수 있게 하자.

입력

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

출력

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

예제 입력 1

4
1
1
1
2

예제 출력 1

3

힌트

예로 주어진 1 1 1 2 는 2번째와 3번째 1을 합쳐서 2로 만들면 1 2 2 가 되고 2 두 개를 합치면 3이 될 수 있다. 그러므로 최대 값은 3이다. 만약에 1번째 2번째 1을 합치면 2 1 2 가 되는데 더 이상 합칠 게 없으므로 최댓값은 2가 되므로 앞에서 한 방법이 최댓값을 얻는 방법이다.

W3sicHJvYmxlbV9pZCI6IjEyMDA4IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiMjYyMTQ0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWJjYTBcdWMyZGNcdWIyOTQgXHVjMmE0XHViOWM4XHVkMmI4IFx1ZDNmMCBcdWFjOGNcdWM3ODRcdWM3NDQgXHVjODhiXHVjNTQ0XHVkNTVjXHViMmU0LiBcdWQ2MDRcdWM3YWMgXHVjN2FjXHViYmY4XHVjNzg4XHVhYzhjIFx1ZDU1OFx1YjI5NCBcdWFjOGNcdWM3ODRcdWM3NDAgXHVjMmRjXHVjNzkxIFx1ZDU2MCBcdWI1NGMsIDF+NDAgXHViYzk0XHVjNzA0XHViOTdjIFx1YWMxNlx1YjI5NCBOKDImbGU7TiZsZTsyNjIsMTQ0KVx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0XHViMzcwIFx1YzVmMFx1YzE4ZFx1YjQxYyBcdWI0NTAgXHVjMjE4XHVhYzAwIFx1YWMxOVx1YzczY1x1YmE3NCBcdWQ1NThcdWIwOThcdWI4NWMgXHVkNTY5XHVjZTYwIFx1YzIxOCBcdWM3ODhcdWIyOTRcdWIzNzAgXHVkNTY5XHVjZTYwIFx1YWNiZFx1YzZiMCBcdWFlMzBcdWM4NzQgXHVhYzEyXHViY2Y0XHViMmU0IDFcdWM3NzQgXHVkMDcwIFx1YzIxOFx1Yjk3YyBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gKFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIDdcdWM3NzQgXHViNDUwIFx1YWMxYyBcdWM1ZjBcdWMxOGRcdWI0MThcdWM1YjQgXHVjNzg4XHVjNzNjXHViYTc0IDhcdWI4NWMgXHVkNTY5XHVjZTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQpPGJyIFwvPlxyXG4mbmJzcDs8YnIgXC8+XHJcblx1YWM4Y1x1Yzc4NFx1Yzc1OCBcdWJhYTlcdWQ0NWNcdWIyOTQgXHVhYzAwXHVjN2E1IFx1ZDA3MCBcdWMyMThcdWI5N2MgXHViOWNjXHViNGRjXHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC4gXHViY2EwXHVjMmRjXHViOTdjIFx1YjNjNFx1YzY0MFx1YzExYyBcdWFjMDBcdWIyYTVcdWQ1NWMgXHVhYzAwXHVjN2E1IFx1ZDA3MCBcdWMyMThcdWI5N2MgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWFjOGMgXHVkNTU4XHVjNzkwLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgTlx1Yzc3NCBcdWM3ODVcdWI4MjVcdWI0MWNcdWIyZTQuIFx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwIE5cdWM5MDRcdWM1ZDAgXHVhYzc4XHVjY2QwIFx1YzgxNVx1YzIxOFx1YWMwMCBcdWM3ODVcdWI4MjVcdWI0MWNcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhYzAwXHVjN2E1IFx1ZDA3MCBcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHViNzdjLjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cdWM2MDhcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0IDEgMSAxIDIgXHViMjk0IDJcdWJjODhcdWM5ZjhcdWM2NDAgM1x1YmM4OFx1YzlmOCAxXHVjNzQ0IFx1ZDU2OVx1Y2NkMFx1YzExYyAyXHViODVjIFx1YjljY1x1YjRlNFx1YmE3NCAxIDIgMiBcdWFjMDAgXHViNDE4XHVhY2UwIDIgXHViNDUwIFx1YWMxY1x1Yjk3YyBcdWQ1NjlcdWNlNThcdWJhNzQgM1x1Yzc3NCBcdWI0MjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVhZGY4XHViN2VjXHViYmMwXHViODVjIFx1Y2Q1Y1x1YjMwMCBcdWFjMTJcdWM3NDAgM1x1Yzc3NFx1YjJlNC4gXHViOWNjXHVjNTdkXHVjNWQwIDFcdWJjODhcdWM5ZjggMlx1YmM4OFx1YzlmOCAxXHVjNzQ0IFx1ZDU2OVx1Y2U1OFx1YmE3NCAyIDEgMiBcdWFjMDAgXHViNDE4XHViMjk0XHViMzcwIFx1YjM1NCBcdWM3NzRcdWMwYzEgXHVkNTY5XHVjZTYwIFx1YWM4YyBcdWM1YzZcdWM3M2NcdWJiYzBcdWI4NWMgXHVjZDVjXHViMzEzXHVhYzEyXHVjNzQwIDJcdWFjMDAgXHViNDE4XHViYmMwXHViODVjIFx1YzU1ZVx1YzVkMFx1YzExYyBcdWQ1NWMgXHViYzI5XHViYzk1XHVjNzc0IFx1Y2Q1Y1x1YjMxM1x1YWMxMlx1Yzc0NCBcdWM1YmJcdWIyOTQgXHViYzI5XHViYzk1XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTIwMDgiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiIyNjIxNDQiLCJkZXNjcmlwdGlvbiI6IjxwPkJlc3NpZSBsaWtlcyBkb3dubG9hZGluZyBnYW1lcyB0byBwbGF5IG9uIGhlciBjZWxsIHBob25lLCBldmVuIHRob3VnaCBzaGUgZG9lcyBmaW5kIHRoZSBzbWFsbCB0b3VjaCBzY3JlZW4gcmF0aGVyIGN1bWJlcnNvbWUgdG8gdXNlIHdpdGggaGVyIGxhcmdlIGhvb3Zlcy48XC9wPlxyXG5cclxuPHA+U2hlIGlzIHBhcnRpY3VsYXJseSBpbnRyaWd1ZWQgYnkgdGhlIGN1cnJlbnQgZ2FtZSBzaGUgaXMgcGxheWluZy4gVGhlIGdhbWUgc3RhcnRzIHdpdGggYSBzZXF1ZW5jZSBvZiBcXChOXFwpIHBvc2l0aXZlIGludGVnZXJzIChcXCgyIFxcbGVxIE4gXFxsZXEgMjYyLDE0NFxcKSksIGVhY2ggaW4gdGhlIHJhbmdlIFxcKDEgXFxsZG90cyA0MFxcKS4gSW4gb25lIG1vdmUsIEJlc3NpZSBjYW4gdGFrZSB0d28gYWRqYWNlbnQgbnVtYmVycyB3aXRoIGVxdWFsIHZhbHVlcyBhbmQgcmVwbGFjZSB0aGVtIGEgc2luZ2xlIG51bWJlciBvZiB2YWx1ZSBvbmUgZ3JlYXRlciAoZS5nLiwgc2hlIG1pZ2h0IHJlcGxhY2UgdHdvIGFkamFjZW50IDdzIHdpdGggYW4gOCkuIFRoZSBnb2FsIGlzIHRvIG1heGltaXplIHRoZSB2YWx1ZSBvZiB0aGUgbGFyZ2VzdCBudW1iZXIgcHJlc2VudCBpbiB0aGUgc2VxdWVuY2UgYXQgdGhlIGVuZCBvZiB0aGUgZ2FtZS4gUGxlYXNlIGhlbHAgQmVzc2llIHNjb3JlIGFzIGhpZ2hseSBhcyBwb3NzaWJsZSE8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIFxcKE5cXCksIGFuZCB0aGUgbmV4dCBcXChOXFwpIGxpbmVzIGdpdmUgdGhlIHNlcXVlbmNlIG9mIFxcKE5cXCkgbnVtYmVycyBhdCB0aGUgc3RhcnQgb2YgdGhlIGdhbWUuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+UGxlYXNlIG91dHB1dCB0aGUgbGFyZ2VzdCBpbnRlZ2VyIEJlc3NpZSBjYW4gZ2VuZXJhdGUuPFwvcD5cclxuIiwiaGludCI6IjxwPkluIHRoaXMgZXhhbXBsZSBzaG93biBoZXJlLCBCZXNzaWUgZmlyc3QgbWVyZ2VzIHRoZSBzZWNvbmQgYW5kIHRoaXJkIDFzIHRvIG9idGFpbiB0aGUgc2VxdWVuY2UgMSAyIDIsIGFuZCB0aGVuIHNoZSBtZXJnZXMgdGhlIDJzIGludG8gYSAzLiBOb3RlIHRoYXQgaXQgaXMgbm90IG9wdGltYWwgdG8gam9pbiB0aGUgZmlyc3QgdHdvIDFzLjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d