시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 944 348 259 40.469%

문제

큰 방에 N개의 풍선이 떠있다. 풍선들은 왼쪽부터 오른쪽까지 일렬로 있다. 진솔이는 화살 가지고 노는 것과 사냥 연습하는 것을 좋아한다. 진솔이는 화살을 왼쪽에서 오른쪽으로 쏜다. 높이는 임의로 선택한다. 화살은 선택된 높이 H에서 풍선을 마주칠 때까지 왼쪽에서 오른쪽으로 이동한다. 화살이 풍선을 마주치는 순간, 풍선은 터지고 사라진다. 화살은 계속해서 가던길을 가는데 높이는 1 줄어든다. 그러므로 만약 화살이 높이 H에서 이동 중이었다면 풍선을 터트린 후에는 높이가 H-1이 된다.

우리의 목표는 모든 풍선을 터트리되 가능한한 적은 화살을 사용하는 것이다.

입력

첫 번째 줄에는 정수 N(1 ≤ N ≤ 1 000 000)이 들어온다.

두 번째 줄에는 배열 Hi가 N개 들어온다.

각각의 Hi(1 ≤ Hi ≤ 1 000 000)는 i번째 풍선의 높이에 해당하며 왼쪽에서 오른쪽으로 나열되는 순서이다.

출력

첫번째 줄 한줄에 최소한 필요한 화살의 갯수를 출력한다.

예제 입력 1

5
2 1 5 4 3

예제 출력 1

2

예제 입력 2

5
1 2 3 4 5

예제 출력 2

5

예제 입력 3

5
4 5 2 1 4

예제 출력 3

3

힌트

첫번째 예제 에서 [5,4,3] 을 터트리고 [2,1]을 터트리면 모든 풍선을 터트릴 수 있으므로 최소한 2개의 화살을 필요로 한다.

W3sicHJvYmxlbV9pZCI6IjExNTA5IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVkNDhkXHVjMTIwIFx1YjlkZVx1Y2Q5NFx1YWUzMCIsImRlc2NyaXB0aW9uIjoiPHA+XHVkMDcwIFx1YmMyOVx1YzVkMCBOXHVhYzFjXHVjNzU4IFx1ZDQ4ZFx1YzEyMFx1Yzc3NCBcdWI1YTBcdWM3ODhcdWIyZTQuIFx1ZDQ4ZFx1YzEyMFx1YjRlNFx1Yzc0MCBcdWM2N2NcdWNhYmRcdWJkODBcdWQxMzAgXHVjNjI0XHViOTc4XHVjYWJkXHVhZTRjXHVjOWMwIFx1Yzc3Y1x1YjgyY1x1Yjg1YyBcdWM3ODhcdWIyZTQuJm5ic3A7XHVjOWM0XHVjMTk0XHVjNzc0XHViMjk0IFx1ZDY1NFx1YzBiNCBcdWFjMDBcdWM5YzBcdWFjZTAgXHViMTc4XHViMjk0IFx1YWM4M1x1YWNmYyBcdWMwYWNcdWIwZTUgXHVjNWYwXHVjMmI1XHVkNTU4XHViMjk0IFx1YWM4M1x1Yzc0NCBcdWM4OGJcdWM1NDRcdWQ1NWNcdWIyZTQuJm5ic3A7XHVjOWM0XHVjMTk0XHVjNzc0XHViMjk0IFx1ZDY1NFx1YzBiNFx1Yzc0NCBcdWM2N2NcdWNhYmRcdWM1ZDBcdWMxMWMgXHVjNjI0XHViOTc4XHVjYWJkXHVjNzNjXHViODVjIFx1YzNkY1x1YjJlNC4gXHViMTkyXHVjNzc0XHViMjk0IFx1Yzc4NFx1Yzc1OFx1Yjg1YyBcdWMxMjBcdWQwZGRcdWQ1NWNcdWIyZTQuJm5ic3A7XHVkNjU0XHVjMGI0XHVjNzQwIFx1YzEyMFx1ZDBkZFx1YjQxYyBcdWIxOTJcdWM3NzQgSFx1YzVkMFx1YzExYyBcdWQ0OGRcdWMxMjBcdWM3NDQgXHViOWM4XHVjOGZjXHVjZTYwIFx1YjU0Y1x1YWU0Y1x1YzljMCZuYnNwO1x1YzY3Y1x1Y2FiZFx1YzVkMFx1YzExYyBcdWM2MjRcdWI5NzhcdWNhYmRcdWM3M2NcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTVjXHViMmU0LiBcdWQ2NTRcdWMwYjRcdWM3NzQgXHVkNDhkXHVjMTIwXHVjNzQ0IFx1YjljOFx1YzhmY1x1Y2U1OFx1YjI5NCBcdWMyMWNcdWFjMDQsIFx1ZDQ4ZFx1YzEyMFx1Yzc0MCBcdWQxMzBcdWM5YzBcdWFjZTAgXHVjMGFjXHViNzdjXHVjOWM0XHViMmU0LiBcdWQ2NTRcdWMwYjRcdWM3NDAgXHVhY2M0XHVjMThkXHVkNTc0XHVjMTFjIFx1YWMwMFx1YjM1OFx1YWUzOFx1Yzc0NCBcdWFjMDBcdWIyOTRcdWIzNzAgXHViMTkyXHVjNzc0XHViMjk0IDEgXHVjOTA0XHVjNWI0XHViNGUwXHViMmU0LiBcdWFkZjhcdWI3ZWNcdWJiYzBcdWI4NWMgXHViOWNjXHVjNTdkIFx1ZDY1NFx1YzBiNFx1Yzc3NCBcdWIxOTJcdWM3NzQgSFx1YzVkMFx1YzExYyBcdWM3NzRcdWIzZDkgXHVjOTExXHVjNzc0XHVjNWM4XHViMmU0XHViYTc0IFx1ZDQ4ZFx1YzEyMFx1Yzc0NCBcdWQxMzBcdWQyYjhcdWI5YjAgXHVkNmM0XHVjNWQwXHViMjk0IFx1YjE5Mlx1Yzc3NFx1YWMwMCBILTFcdWM3NzQgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2YjBcdWI5YWNcdWM3NTggXHViYWE5XHVkNDVjXHViMjk0IFx1YmFhOFx1YjRlMCBcdWQ0OGRcdWMxMjBcdWM3NDQgXHVkMTMwXHVkMmI4XHViOWFjXHViNDE4IFx1YWMwMFx1YjJhNVx1ZDU1Y1x1ZDU1YyBcdWM4MDFcdWM3NDAgXHVkNjU0XHVjMGI0XHVjNzQ0IFx1YzBhY1x1YzZhOVx1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM4MTVcdWMyMTggTigxICZsZTsgTiAmbGU7Jm5ic3A7MSAwMDAgMDAwKVx1Yzc3NCBcdWI0ZTRcdWM1YjRcdWM2MjhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YmMzMFx1YzVmNCZuYnNwO0g8c3ViPmk8XC9zdWI+XHVhYzAwIE5cdWFjMWMgXHViNGU0XHVjNWI0XHVjNjI4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDFcdWFjMDFcdWM3NTggSDxzdWI+aTxcL3N1Yj4oMSAmbGU7IEg8c3ViPmk8XC9zdWI+Jm5ic3A7JmxlOyZuYnNwOzEgMDAwIDAwMClcdWIyOTQgaVx1YmM4OFx1YzlmOCBcdWQ0OGRcdWMxMjBcdWM3NTggXHViMTkyXHVjNzc0XHVjNWQwIFx1ZDU3NFx1YjJmOVx1ZDU1OFx1YmE3MCBcdWM2N2NcdWNhYmRcdWM1ZDBcdWMxMWMgXHVjNjI0XHViOTc4XHVjYWJkXHVjNzNjXHViODVjIFx1YjA5OFx1YzVmNFx1YjQxOFx1YjI5NCBcdWMyMWNcdWMxMWNcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHViYzg4XHVjOWY4IFx1YzkwNCBcdWQ1NWNcdWM5MDRcdWM1ZDAgXHVjZDVjXHVjMThjXHVkNTVjIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWQ2NTRcdWMwYjRcdWM3NTggXHVhYzJmXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+XHVjY2FiXHViYzg4XHVjOWY4IFx1YzYwOFx1YzgxYyZuYnNwO1x1YzVkMFx1YzExYyBbNSw0LDNdIFx1Yzc0NCBcdWQxMzBcdWQyYjhcdWI5YWNcdWFjZTAgWzIsMV1cdWM3NDQgXHVkMTMwXHVkMmI4XHViOWFjXHViYTc0IFx1YmFhOFx1YjRlMCBcdWQ0OGRcdWMxMjBcdWM3NDQgXHVkMTMwXHVkMmI4XHViOWI0IFx1YzIxOCBcdWM3ODhcdWM3M2NcdWJiYzBcdWI4NWMgXHVjZDVjXHVjMThjXHVkNTVjIDJcdWFjMWNcdWM3NTggXHVkNjU0XHVjMGI0XHVjNzQ0IFx1ZDU0NFx1YzY5NFx1Yjg1YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxMTUwOSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkJBTE9OSSIsImRlc2NyaXB0aW9uIjoiPHA+VGhlcmUgYXJlIE4gYmFsbG9vbnMgZmxvYXRpbmcgaW4gdGhlIGFpciBpbiBhIGxhcmdlIHJvb20sIGxpbmVkIHVwIGZyb20gbGVmdCB0byByaWdodC4gWW91bmcgUGVyaWNhIGxpa2VzIHRvIHBsYXkgd2l0aCBhcnJvd3MgYW5kIHByYWN0aWNlIGhpcyBodW50aW5nIGFiaWxpdGllcy4gSGUgc2hvb3RzIGFuIGFycm93IGZyb20gdGhlIGxlZnQgdG8gdGhlIHJpZ2h0IHNpZGUgb2YgdGhlIHJvb20gZnJvbSBhbiBhcmJpdHJhcnkgaGVpZ2h0IGhlIGNob29zZXMuIFRoZSBhcnJvdyBtb3ZlcyBmcm9tIGxlZnQgdG8gcmlnaHQsIGF0IGEgY2hvc2VuIGhlaWdodCBIIHVudGlsIGl0IGZpbmRzIGEgYmFsbG9vbi4gVGhlIG1vbWVudCB3aGVuIGFuIGFycm93IHRvdWNoZXMgYSBiYWxsb29uLCB0aGUgYmFsbG9vbiBwb3BzIGFuZCBkaXNhcHBlYXJzIGFuZCB0aGUgYXJyb3cgY29udGludWVzIGl0cyB3YXkgZnJvbSBsZWZ0IHRvIHJpZ2h0IGF0IGEgaGVpZ2h0IGRlY3JlYXNlZCBieSAxLiBUaGVyZWZvcmUsIGlmIHRoZSBhcnJvdyB3YXMgbW92aW5nIGF0IGhlaWdodCBILCBhZnRlciBwb3BwaW5nIHRoZSBiYWxsb29uIGl0IHRyYXZlbHMgb24gaGVpZ2h0IEgtMS48XC9wPlxyXG5cclxuPHA+T3VyIGhlcm8mcnNxdW87cyBnb2FsIGlzIHRvIHBvcCBhbGwgdGhlIGJhbGxvb25zIHVzaW5nIGFzIGxpdHRsZSBhcnJvd3MgYXMgcG9zc2libGUuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyB0aGUgaW50ZWdlciBOICgxICZsZTsgTiAmbGU7IDEgMDAwIDAwMCkuPFwvcD5cclxuXHJcbjxwPlRoZSBzZWNvbmQgbGluZSBvZiBpbnB1dCBjb250YWlucyBhbiBhcnJheSBvZiBOIGludGVnZXJzIEg8c3ViPmk8XC9zdWI+LjxcL3A+XHJcblxyXG48cD5FYWNoIGludGVnZXIgSDxzdWI+aTxcL3N1Yj4gKDEgJmxlOyBIPHN1Yj5pPFwvc3ViPiAmbGU7IDEgMDAwIDAwMCkgaXMgdGhlIGhlaWdodCBhdCB3aGljaCB0aGUgaSB0aCBiYWxsb29uIGZsb2F0cywgcmVzcGVjdGl2ZWx5IGZyb20gbGVmdCB0byByaWdodC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgZmlyc3QgYW5kIG9ubHkgbGluZSBvZiBvdXRwdXQgbXVzdCBjb250YWluIHRoZSBtaW5pbWFsIG51bWJlciBvZiB0aW1lcyBQZXJvIG5lZWRzIHRvIHNob290IGFuIGFycm93IHNvIHRoYXQgYWxsIGJhbGxvb25zIGFyZSBwb3BwZWQuPFwvcD5cclxuIiwiaGludCI6IjxwPkNsYXJpZmljYXRpb24gb2YgdGhlIGZpcnN0IGV4YW1wbGU6IE91ciBoZXJvIHNob290cyB0aGUgYXJyb3cgYXQgaGVpZ2h0IDUgLSB3aGljaCBkZXN0cm95cyBbNSwgNCwgM10sIGFuZCBzaG9vdHMgYW4gYXJyb3cgYXQgaGVpZ2h0IDIgLSB3aGljaCBkZXN0cm95cyBbMiwgMV0uPFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Contest > Croatian Open Competition in Informatics > COCI 2015/2016 > Contest #1 3번