시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 446 127 116 34.940%

문제

알고리즘 게임 행사의 성대한 개최를 위하여, 일렬로 들어선 타워들의 철거를 하려고 한다. 최초 계획은 각 타워를 구성하는 블록을 폭파시키려 했지만 시간 문제로 조금 더 빠른 방법이 필요하다.

상근이에게는 블록들의 빠른 제거를 위하여 Kinetic / Incandescent Energy Particle Cannon(이하 UKIEPC)가 주어졌다. UKIEPC는 한번의 충전으로 타워 하나의 모든 층 또는 상근이가 선택한 모든 타워들의 x번째 층을 동시에 제거 할 수있다. 후자의 경우에는 만약 상근이가 선택한 x 보다 높이가 낮은 블록들은 그대로 남아 있고, 그보다 높은 경우에는 x번째 층이 제거되며 나머지 블록들은 한층씩 아래로 내려온다.

각 타워들의 층수가 주어질 때, 모든 블록들을 제거하기 위한 최소의 UKIEPC 충전 횟수를 구하시오.

입력

첫줄에는 타워의 수 n(2 ≤ n ≤ 100 000)가, 두 번째 줄에는 n개의 타워에 대한 각각의 블록의 수 hi ( i = 1, 2, ... , n, 1 ≤ hi ≤ 1 000 000)가 주어진다.

출력

출력은 하나의 줄에 모든 블록을 제거할 수 있는 최소의 충전 횟수를 출력 하시오.

예제 입력 1

6
2 1 8 8 2 3

예제 출력 1

5

예제 입력 2

5
1 1 1 1 10

예제 출력 2

2

힌트

hi 높이를 가지는 타워는 총 hi 개 블록으로 구성됨 (1* hi 모양의 직사각형)

W3sicHJvYmxlbV9pZCI6IjEwMjYzIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVhYzFjXHVkNjhjXHVjMmRkIiwiZGVzY3JpcHRpb24iOiI8cD4gXHVjNTRjXHVhY2UwXHViOWFjXHVjOTk4IFx1YWM4Y1x1Yzc4NCBcdWQ1ODlcdWMwYWNcdWM3NTggXHVjMTMxXHViMzAwXHVkNTVjIFx1YWMxY1x1Y2Q1Y1x1Yjk3YyBcdWM3MDRcdWQ1NThcdWM1ZWMsIFx1Yzc3Y1x1YjgyY1x1Yjg1YyBcdWI0ZTRcdWM1YjRcdWMxMjAgXHVkMGMwXHVjNmNjXHViNGU0XHVjNzU4IFx1Y2NhMFx1YWM3MFx1Yjk3YyBcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWNkNWNcdWNkMDggXHVhY2M0XHVkNjhkXHVjNzQwIFx1YWMwMSBcdWQwYzBcdWM2Y2NcdWI5N2MgXHVhZDZjXHVjMTMxXHVkNTU4XHViMjk0IFx1YmUxNFx1Yjg1ZFx1Yzc0NCBcdWQzZWRcdWQzMGNcdWMyZGNcdWQwYTRcdWI4MjQgXHVkNTg4XHVjOWMwXHViOWNjIFx1YzJkY1x1YWMwNCBcdWJiMzhcdWM4MWNcdWI4NWMgXHVjODcwXHVhZTA4IFx1YjM1NCBcdWJlNjBcdWI5NzggXHViYzI5XHViYzk1XHVjNzc0IFx1ZDU0NFx1YzY5NFx1ZDU1OFx1YjJlNC5cclxuPFwvcD5cclxuPHA+IFx1YzBjMVx1YWRmY1x1Yzc3NFx1YzVkMFx1YWM4Y1x1YjI5NCBcdWJlMTRcdWI4NWRcdWI0ZTRcdWM3NTggXHViZTYwXHViOTc4IFx1YzgxY1x1YWM3MFx1Yjk3YyBcdWM3MDRcdWQ1NThcdWM1ZWMgS2luZXRpYyBcLyBJbmNhbmRlc2NlbnQgRW5lcmd5IFBhcnRpY2xlIENhbm5vbihcdWM3NzRcdWQ1NTggVUtJRVBDKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWIyZTQuIFVLSUVQQ1x1YjI5NCBcdWQ1NWNcdWJjODhcdWM3NTggXHVjZGE5XHVjODA0XHVjNzNjXHViODVjIFx1ZDBjMFx1YzZjYyBcdWQ1NThcdWIwOThcdWM3NTggXHViYWE4XHViNGUwIFx1Y2UzNSBcdWI2MTBcdWIyOTQgXHVjMGMxXHVhZGZjXHVjNzc0XHVhYzAwIFx1YzEyMFx1ZDBkZFx1ZDU1YyBcdWJhYThcdWI0ZTAgXHVkMGMwXHVjNmNjXHViNGU0XHVjNzU4IHhcdWJjODhcdWM5ZjggXHVjZTM1XHVjNzQ0IFx1YjNkOVx1YzJkY1x1YzVkMCBcdWM4MWNcdWFjNzAgXHVkNTYwIFx1YzIxOFx1Yzc4OFx1YjJlNC4gIFx1ZDZjNFx1Yzc5MFx1Yzc1OCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHViOWNjXHVjNTdkIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YWMwMCBcdWMxMjBcdWQwZGRcdWQ1NWMgeCBcdWJjZjRcdWIyZTQgXHViMTkyXHVjNzc0XHVhYzAwIFx1YjBhZVx1Yzc0MCBcdWJlMTRcdWI4NWRcdWI0ZTRcdWM3NDAgXHVhZGY4XHViMzAwXHViODVjIFx1YjBhOFx1YzU0NCBcdWM3ODhcdWFjZTAsIFx1YWRmOFx1YmNmNFx1YjJlNCBcdWIxOTJcdWM3NDAgXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IHhcdWJjODhcdWM5ZjggXHVjZTM1XHVjNzc0IFx1YzgxY1x1YWM3MFx1YjQxOFx1YmE3MCBcdWIwOThcdWJhMzhcdWM5YzAgXHViZTE0XHViODVkXHViNGU0XHVjNzQwIFx1ZDU1Y1x1Y2UzNVx1YzUyOSBcdWM1NDRcdWI3OThcdWI4NWMgXHViMGI0XHViODI0XHVjNjI4XHViMmU0LlxyXG48XC9wPiBcdWFjMDEgXHVkMGMwXHVjNmNjXHViNGU0XHVjNzU4IFx1Y2UzNVx1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzggXHViNTRjLCBcdWJhYThcdWI0ZTAgXHViZTE0XHViODVkXHViNGU0XHVjNzQ0IFx1YzgxY1x1YWM3MFx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NWMgXHVjZDVjXHVjMThjXHVjNzU4IFVLSUVQQyBcdWNkYTlcdWM4MDQgXHVkNjlmXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YzJkY1x1YzYyNC4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzkwNFx1YzVkMFx1YjI5NCBcdWQwYzBcdWM2Y2NcdWM3NTggXHVjMjE4IG4oMiAmbGU7IG4gJmxlOyAxMDAgMDAwKVx1YWMwMCwgXHViNDUwIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgblx1YWMxY1x1Yzc1OCBcdWQwYzBcdWM2Y2NcdWM1ZDAgXHViMzAwXHVkNTVjIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWJlMTRcdWI4NWRcdWM3NTggXHVjMjE4IGg8c3ViPmkgPFwvc3ViPiggaSA9IDEsIDIsIC4uLiAsIG4sIDEgJmxlOyBoPHN1Yj5pPFwvc3ViPiAmbGU7IDEgMDAwIDAwMClcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2Q5Y1x1YjgyNVx1Yzc0MCBcdWQ1NThcdWIwOThcdWM3NTggXHVjOTA0XHVjNWQwIFx1YmFhOFx1YjRlMCBcdWJlMTRcdWI4NWRcdWM3NDQgXHVjODFjXHVhYzcwXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjZDVjXHVjMThjXHVjNzU4IFx1Y2RhOVx1YzgwNCBcdWQ2OWZcdWMyMThcdWI5N2MgXHVjZDljXHViODI1IFx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+aDxzdWI+aSA8XC9zdWI+XHViMTkyXHVjNzc0XHViOTdjIFx1YWMwMFx1YzljMFx1YjI5NCBcdWQwYzBcdWM2Y2NcdWIyOTQgXHVjZDFkIGg8c3ViPmkgPFwvc3ViPlx1YWMxYyBcdWJlMTRcdWI4NWRcdWM3M2NcdWI4NWMgXHVhZDZjXHVjMTMxXHViNDI4ICgxKiBoPHN1Yj5pIDxcL3N1Yj5cdWJhYThcdWM1OTFcdWM3NTggXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1KTxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTAyNjMiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJPcGVuaW5nIENlcmVtb255IiwiZGVzY3JpcHRpb24iOiI8cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXMyXC9vcGVuaW5nLnBuZ1wiIHN0eWxlPVwiZmxvYXQ6cmlnaHQ7IGhlaWdodDoyMTBweDsgd2lkdGg6MjQ5cHhcIiBcLz5Gb3IgdGhlIGdyYW5kIG9wZW5pbmcgb2YgdGhlIGFsZ29yaXRobWljIGdhbWVzIGluIE5sb2dOc2dsb3csIGEgcm93IG9mIHRvd2VyIGJsb2NrcyBpcyBzZXQgdG8gYmUgZGVtb2xpc2hlZCBpbiBhIGdyYW5kIGRlbW9uc3RyYXRpb24gb2YgcmVuZXdhbC4gT3JpZ2luYWxseSB0aGUgcGxhbiB3YXMgdG8gYWNjb21wbGlzaCB0aGlzIHdpdGggY29udHJvbGxlZCBleHBsb3Npb25zLCBvbmUgZm9yIGVhY2ggdG93ZXIgYmxvY2ssIGJ1dCB0aW1lIGNvbnN0cmFpbnRzIG5vdyByZXF1aXJlIGEgaGFzdGllciBzb2x1dGlvbi48XC9wPlxyXG5cclxuPHA+VG8gaGVscCB5b3UgcmVtb3ZlIHRoZSBibG9ja3MgbW9yZSByYXBpZGx5IHlvdSBoYXZlIGJlZW4gZ2l2ZW4gdGhlIHVzZSBvZiBhIFVuaXZlcnNhbCBLaW5ldGljIFwvIEluY2FuZGVzY2VudCBFbmVyZ3kgUGFydGljbGUgQ2Fubm9uIChVS0lFUEMpLiBPbiBhIHNpbmdsZSBjaGFyZ2UsIHRoaXMgY3V0dGluZy1lZGdlIGNvbnRyYXB0aW9uIGNhbiByZW1vdmUgZWl0aGVyIGFsbCBvZiB0aGUgZmxvb3JzIGluIGEgc2luZ2xlIHRvd2VyIGJsb2NrLCBvciBhbGwgdGhlIHgtdGggZmxvb3JzIGluIGFsbCB0aGUgYmxvY2tzIHNpbXVsdGFuZW91c2x5LCBmb3IgdXNlciZyc3F1bztzIGNob2ljZSBvZiB0aGUgZmxvb3IgbnVtYmVyIHguIEluIHRoZSBsYXR0ZXIgY2FzZSwgdGhlIGJsb2NrcyB0aGF0IGFyZSBsZXNzIHRoYW4geCBmbG9vcnMgaGlnaCBhcmUgbGVmdCB1bnRvdWNoZWQsIHdoaWxlIGZvciBibG9ja3MgaGF2aW5nIG1vcmUgdGhhbiB4IGZsb29ycywgYWxsIHRoZSBmbG9vcnMgYWJvdmUgdGhlIHJlbW92ZWQgeC10aCBvbmUgZmFsbCBkb3duIGJ5IG9uZSBsZXZlbC48XC9wPlxyXG5cclxuPHA+R2l2ZW4gdGhlIG51bWJlciBvZiBmbG9vcnMgb2YgYWxsIHRvd2Vycywgb3V0cHV0IHRoZSBtaW5pbXVtIG51bWJlciBvZiBjaGFyZ2VzIG5lZWRlZCB0byBlbGltaW5hdGUgYWxsIGZsb29ycyBvZiBhbGwgYmxvY2tzLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdGhlIG51bWJlciBvZiBibG9ja3Mgbiwgd2hlcmUgMiAmbGU7IG4gJmxlOyAxMDAgMDAwLiBUaGUgc2Vjb25kIGxpbmUgY29udGFpbnMgbiBjb25zZWN1dGl2ZSBibG9jayBoZWlnaHRzIGg8c3ViPmk8XC9zdWI+IGZvciBpID0gMSwgMiwgLi4uICwgbiwgd2hlcmUgMSAmbGU7IGg8c3ViPmk8XC9zdWI+ICZsZTsgMSAwMDAgMDAwLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCBvbmUgbGluZSBjb250YWluaW5nIG9uZSBpbnRlZ2VyOiB0aGUgbWluaW11bSBudW1iZXIgb2YgY2hhcmdlcyBuZWVkZWQgdG8gdGVhciBkb3duIGFsbCB0aGUgYmxvY2tzLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==