시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 1041 399 286 40.857%

문제

큰 방에 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+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDQgXHVkNTVjXHVjOTA0XHVjNWQwIFx1Y2Q1Y1x1YzE4Y1x1ZDU1YyBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVkNjU0XHVjMGI0XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjNjA4XHVjODFjJm5ic3A7XHVjNWQwXHVjMTFjIFs1LDQsM10gXHVjNzQ0IFx1ZDEzMFx1ZDJiOFx1YjlhY1x1YWNlMCBbMiwxXVx1Yzc0NCBcdWQxMzBcdWQyYjhcdWI5YWNcdWJhNzQgXHViYWE4XHViNGUwIFx1ZDQ4ZFx1YzEyMFx1Yzc0NCBcdWQxMzBcdWQyYjhcdWI5YjQgXHVjMjE4IFx1Yzc4OFx1YzczY1x1YmJjMFx1Yjg1YyBcdWNkNWNcdWMxOGNcdWQ1NWMgMlx1YWMxY1x1Yzc1OCBcdWQ2NTRcdWMwYjRcdWM3NDQgXHVkNTQ0XHVjNjk0XHViODVjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjExNTA5IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQkFMT05JIiwiZGVzY3JpcHRpb24iOiI8cD5UaGVyZSBhcmUgTiBiYWxsb29ucyBmbG9hdGluZyBpbiB0aGUgYWlyIGluIGEgbGFyZ2Ugcm9vbSwgbGluZWQgdXAgZnJvbSBsZWZ0IHRvIHJpZ2h0LiBZb3VuZyBQZXJpY2EgbGlrZXMgdG8gcGxheSB3aXRoIGFycm93cyBhbmQgcHJhY3RpY2UgaGlzIGh1bnRpbmcgYWJpbGl0aWVzLiBIZSBzaG9vdHMgYW4gYXJyb3cgZnJvbSB0aGUgbGVmdCB0byB0aGUgcmlnaHQgc2lkZSBvZiB0aGUgcm9vbSBmcm9tIGFuIGFyYml0cmFyeSBoZWlnaHQgaGUgY2hvb3Nlcy4gVGhlIGFycm93IG1vdmVzIGZyb20gbGVmdCB0byByaWdodCwgYXQgYSBjaG9zZW4gaGVpZ2h0IEggdW50aWwgaXQgZmluZHMgYSBiYWxsb29uLiBUaGUgbW9tZW50IHdoZW4gYW4gYXJyb3cgdG91Y2hlcyBhIGJhbGxvb24sIHRoZSBiYWxsb29uIHBvcHMgYW5kIGRpc2FwcGVhcnMgYW5kIHRoZSBhcnJvdyBjb250aW51ZXMgaXRzIHdheSBmcm9tIGxlZnQgdG8gcmlnaHQgYXQgYSBoZWlnaHQgZGVjcmVhc2VkIGJ5IDEuIFRoZXJlZm9yZSwgaWYgdGhlIGFycm93IHdhcyBtb3ZpbmcgYXQgaGVpZ2h0IEgsIGFmdGVyIHBvcHBpbmcgdGhlIGJhbGxvb24gaXQgdHJhdmVscyBvbiBoZWlnaHQgSC0xLjxcL3A+XHJcblxyXG48cD5PdXIgaGVybyZyc3F1bztzIGdvYWwgaXMgdG8gcG9wIGFsbCB0aGUgYmFsbG9vbnMgdXNpbmcgYXMgbGl0dGxlIGFycm93cyBhcyBwb3NzaWJsZS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHRoZSBpbnRlZ2VyIE4gKDEgJmxlOyBOICZsZTsgMSAwMDAgMDAwKS48XC9wPlxyXG5cclxuPHA+VGhlIHNlY29uZCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIGFuIGFycmF5IG9mIE4gaW50ZWdlcnMgSDxzdWI+aTxcL3N1Yj4uPFwvcD5cclxuXHJcbjxwPkVhY2ggaW50ZWdlciBIPHN1Yj5pPFwvc3ViPiAoMSAmbGU7IEg8c3ViPmk8XC9zdWI+ICZsZTsgMSAwMDAgMDAwKSBpcyB0aGUgaGVpZ2h0IGF0IHdoaWNoIHRoZSBpIHRoIGJhbGxvb24gZmxvYXRzLCByZXNwZWN0aXZlbHkgZnJvbSBsZWZ0IHRvIHJpZ2h0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBmaXJzdCBhbmQgb25seSBsaW5lIG9mIG91dHB1dCBtdXN0IGNvbnRhaW4gdGhlIG1pbmltYWwgbnVtYmVyIG9mIHRpbWVzIFBlcm8gbmVlZHMgdG8gc2hvb3QgYW4gYXJyb3cgc28gdGhhdCBhbGwgYmFsbG9vbnMgYXJlIHBvcHBlZC48XC9wPlxyXG4iLCJoaW50IjoiPHA+Q2xhcmlmaWNhdGlvbiBvZiB0aGUgZmlyc3QgZXhhbXBsZTogT3VyIGhlcm8gc2hvb3RzIHRoZSBhcnJvdyBhdCBoZWlnaHQgNSAtIHdoaWNoIGRlc3Ryb3lzIFs1LCA0LCAzXSwgYW5kIHNob290cyBhbiBhcnJvdyBhdCBoZWlnaHQgMiAtIHdoaWNoIGRlc3Ryb3lzIFsyLCAxXS48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

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