시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 418 119 109 35.275%

문제

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

상근이에게는 블록들의 빠른 제거를 위하여 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+IFx1YzBjMVx1YWRmY1x1Yzc3NFx1YzVkMFx1YWM4Y1x1YjI5NCBcdWJlMTRcdWI4NWRcdWI0ZTRcdWM3NTggXHViZTYwXHViOTc4IFx1YzgxY1x1YWM3MFx1Yjk3YyBcdWM3MDRcdWQ1NThcdWM1ZWMgS2luZXRpYyBcLyBJbmNhbmRlc2NlbnQgRW5lcmd5IFBhcnRpY2xlIENhbm5vbihcdWM3NzRcdWQ1NTggVUtJRVBDKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWIyZTQuIFVLSUVQQ1x1YjI5NCBcdWQ1NWNcdWJjODhcdWM3NTggXHVjZGE5XHVjODA0XHVjNzNjXHViODVjIFx1ZDBjMFx1YzZjYyBcdWQ1NThcdWIwOThcdWM3NTggXHViYWE4XHViNGUwIFx1Y2UzNSBcdWI2MTBcdWIyOTQgXHVjMGMxXHVhZGZjXHVjNzc0XHVhYzAwIFx1YzEyMFx1ZDBkZFx1ZDU1YyBcdWJhYThcdWI0ZTAgXHVkMGMwXHVjNmNjXHViNGU0XHVjNzU4IHhcdWJjODhcdWM5ZjggXHVjZTM1XHVjNzQ0IFx1YjNkOVx1YzJkY1x1YzVkMCBcdWM4MWNcdWFjNzAgXHVkNTYwIFx1YzIxOFx1Yzc4OFx1YjJlNC4gIFx1ZDZjNFx1Yzc5MFx1Yzc1OCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHViOWNjXHVjNTdkIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YWMwMCBcdWMxMjBcdWQwZGRcdWQ1NWMgeCBcdWJjZjRcdWIyZTQgXHViMTkyXHVjNzc0XHVhYzAwIFx1YjBhZVx1Yzc0MCBcdWJlMTRcdWI4NWRcdWI0ZTRcdWM3NDAgXHVhZGY4XHViMzAwXHViODVjIFx1YjBhOFx1YzU0NCBcdWM3ODhcdWFjZTAsIFx1YWRmOFx1YmNmNFx1YjJlNCBcdWIxOTJcdWM3NDAgXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IHhcdWJjODhcdWM5ZjggXHVjZTM1XHVjNzc0IFx1YzgxY1x1YWM3MFx1YjQxOFx1YmE3MCBcdWIwOThcdWJhMzhcdWM5YzAgXHViZTE0XHViODVkXHViNGU0XHVjNzQwIFx1ZDU1Y1x1Y2UzNVx1YzUyOSBcdWM1NDRcdWI3OThcdWI4NWMgXHViMGI0XHViODI0XHVjNjI4XHViMmU0LlxyXG48XC9wPiBcdWFjMDEgXHVkMGMwXHVjNmNjXHViNGU0XHVjNzU4IFx1Y2UzNVx1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzggXHViNTRjLCBcdWJhYThcdWI0ZTAgXHViZTE0XHViODVkXHViNGU0XHVjNzQ0IFx1YzgxY1x1YWM3MFx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NWMgXHVjZDVjXHVjMThjXHVjNzU4IFVLSUVQQyBcdWNkYTlcdWM4MDQgXHVkNjlmXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YzJkY1x1YzYyNC4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzkwNFx1YzVkMFx1YjI5NCBcdWQwYzBcdWM2Y2NcdWM3NTggXHVjMjE4IG4oMiAmbGU7IG4gJmxlOyAxMDAgMDAwKVx1YWMwMCwgXHViNDUwXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBuXHVhYzFjXHVjNzU4IFx1ZDBjMFx1YzZjY1x1YzVkMCBcdWIzMDBcdWQ1NWMgXHVhYzAxXHVhYzAxXHVjNzU4IFx1YmUxNFx1Yjg1ZFx1Yzc1OCBcdWMyMTggaDxzdWI+aSA8XC9zdWI+KCBpID0gMSwgMiwgLi4uICwgbiwgMSAmbGU7IGg8c3ViPmk8XC9zdWI+ICZsZTsgMSAwMDAgMDAwKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjZDljXHViODI1XHVjNzQwIFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWM5MDRcdWM1ZDAgXHViYWE4XHViNGUwIFx1YmUxNFx1Yjg1ZFx1Yzc0NCBcdWM4MWNcdWFjNzBcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWNkNWNcdWMxOGNcdWM3NTggXHVjZGE5XHVjODA0IFx1ZDY5Zlx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjUgXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5oPHN1Yj5pIDxcL3N1Yj5cdWIxOTJcdWM3NzRcdWI5N2MgXHVhYzAwXHVjOWMwXHViMjk0IFx1ZDBjMFx1YzZjY1x1YjI5NCBcdWNkMWQgaDxzdWI+aSA8XC9zdWI+XHVhYzFjIFx1YmUxNFx1Yjg1ZFx1YzczY1x1Yjg1YyBcdWFkNmNcdWMxMzFcdWI0MjggKDEqIGg8c3ViPmkgPFwvc3ViPlx1YmFhOFx1YzU5MVx1Yzc1OCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTUpPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxMDI2MyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ik9wZW5pbmcgQ2VyZW1vbnkiLCJkZXNjcmlwdGlvbiI6IjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlczJcL29wZW5pbmcucG5nXCIgc3R5bGU9XCJmbG9hdDpyaWdodDsgaGVpZ2h0OjIxMHB4OyB3aWR0aDoyNDlweFwiIFwvPkZvciB0aGUgZ3JhbmQgb3BlbmluZyBvZiB0aGUgYWxnb3JpdGhtaWMgZ2FtZXMgaW4gTmxvZ05zZ2xvdywgYSByb3cgb2YgdG93ZXIgYmxvY2tzIGlzIHNldCB0byBiZSBkZW1vbGlzaGVkIGluIGEgZ3JhbmQgZGVtb25zdHJhdGlvbiBvZiByZW5ld2FsLiBPcmlnaW5hbGx5IHRoZSBwbGFuIHdhcyB0byBhY2NvbXBsaXNoIHRoaXMgd2l0aCBjb250cm9sbGVkIGV4cGxvc2lvbnMsIG9uZSBmb3IgZWFjaCB0b3dlciBibG9jaywgYnV0IHRpbWUgY29uc3RyYWludHMgbm93IHJlcXVpcmUgYSBoYXN0aWVyIHNvbHV0aW9uLjxcL3A+XHJcblxyXG48cD5UbyBoZWxwIHlvdSByZW1vdmUgdGhlIGJsb2NrcyBtb3JlIHJhcGlkbHkgeW91IGhhdmUgYmVlbiBnaXZlbiB0aGUgdXNlIG9mIGEgVW5pdmVyc2FsIEtpbmV0aWMgXC8gSW5jYW5kZXNjZW50IEVuZXJneSBQYXJ0aWNsZSBDYW5ub24gKFVLSUVQQykuIE9uIGEgc2luZ2xlIGNoYXJnZSwgdGhpcyBjdXR0aW5nLWVkZ2UgY29udHJhcHRpb24gY2FuIHJlbW92ZSBlaXRoZXIgYWxsIG9mIHRoZSBmbG9vcnMgaW4gYSBzaW5nbGUgdG93ZXIgYmxvY2ssIG9yIGFsbCB0aGUgeC10aCBmbG9vcnMgaW4gYWxsIHRoZSBibG9ja3Mgc2ltdWx0YW5lb3VzbHksIGZvciB1c2VyJnJzcXVvO3MgY2hvaWNlIG9mIHRoZSBmbG9vciBudW1iZXIgeC4gSW4gdGhlIGxhdHRlciBjYXNlLCB0aGUgYmxvY2tzIHRoYXQgYXJlIGxlc3MgdGhhbiB4IGZsb29ycyBoaWdoIGFyZSBsZWZ0IHVudG91Y2hlZCwgd2hpbGUgZm9yIGJsb2NrcyBoYXZpbmcgbW9yZSB0aGFuIHggZmxvb3JzLCBhbGwgdGhlIGZsb29ycyBhYm92ZSB0aGUgcmVtb3ZlZCB4LXRoIG9uZSBmYWxsIGRvd24gYnkgb25lIGxldmVsLjxcL3A+XHJcblxyXG48cD5HaXZlbiB0aGUgbnVtYmVyIG9mIGZsb29ycyBvZiBhbGwgdG93ZXJzLCBvdXRwdXQgdGhlIG1pbmltdW0gbnVtYmVyIG9mIGNoYXJnZXMgbmVlZGVkIHRvIGVsaW1pbmF0ZSBhbGwgZmxvb3JzIG9mIGFsbCBibG9ja3MuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyB0aGUgbnVtYmVyIG9mIGJsb2NrcyBuLCB3aGVyZSAyICZsZTsgbiAmbGU7IDEwMCAwMDAuIFRoZSBzZWNvbmQgbGluZSBjb250YWlucyBuIGNvbnNlY3V0aXZlIGJsb2NrIGhlaWdodHMgaDxzdWI+aTxcL3N1Yj4gZm9yIGkgPSAxLCAyLCAuLi4gLCBuLCB3aGVyZSAxICZsZTsgaDxzdWI+aTxcL3N1Yj4gJmxlOyAxIDAwMCAwMDAuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IG9uZSBsaW5lIGNvbnRhaW5pbmcgb25lIGludGVnZXI6IHRoZSBtaW5pbXVtIG51bWJlciBvZiBjaGFyZ2VzIG5lZWRlZCB0byB0ZWFyIGRvd24gYWxsIHRoZSBibG9ja3MuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d