시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 111 23 19 32.759%

문제

나코더 회원들은 재민이의 생일을 축하하기 위해, 열심히 생일 케이크를 만들고 있다.

케이크를 만들기 위해서 현재 길이 Wi, 높이 1인 빵조각이 1 ~ N 순서대로 만들어지고 있다. 나코더 회원들은 이 빵조각들을 모두 쌓아서 (버리면 안된다) 층층이 케이크를 만들고자 한다.

케이크는 여러 층으로 구성될 수 있는데, 한 층의 길이는 그 층에 있는 빵조각의 길이의 합이며, 위에 있는 층의 길이가 아래에 있는 층의 길이보다 클 수 없다. (그러면, 케익이 무너지고 말 것이다!)

또한, 나중에 만들어진 빵조각은 전에 만들어진 빵조각보다 낮은 층에 올라갈 수 없다.

이를 만족하는 선에서 최대한의 높이로 케익을 쌓고자 할때, 과연 몇층까지 쌓을 수 있을까?

입력

첫번째 줄에 N이 주어진다. (1 <= N <= 100000)

이후 N개의 줄에 Wi가 주어진다 (1 <= Wi <= 10000)

출력

가장 높은 케이크의 크기를 출력하라.

예제 입력 1

3
1
2
3

예제 출력 1

2

힌트

다음과 같은 구성이 가능하다.

 +----------+
 |    3     | 
 +---+------+ 
 | 1 |   2  | 
 +---+------+
W3sicHJvYmxlbV9pZCI6IjYxMTYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNmMDBcdWM3NzRcdWQwNmMiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YjA5OFx1Y2Y1NFx1YjM1NCBcdWQ2OGNcdWM2ZDBcdWI0ZTRcdWM3NDAgXHVjN2FjXHViYmZjXHVjNzc0XHVjNzU4IFx1YzBkZFx1Yzc3Y1x1Yzc0NCBcdWNkOTVcdWQ1NThcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0LCBcdWM1ZjRcdWMyZWNcdWQ3ODggXHVjMGRkXHVjNzdjIFx1Y2YwMFx1Yzc3NFx1ZDA2Y1x1Yjk3YyBcdWI5Y2NcdWI0ZTRcdWFjZTAgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWNmMDBcdWM3NzRcdWQwNmNcdWI5N2MgXHViOWNjXHViNGU0XHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExYyBcdWQ2MDRcdWM3YWMgXHVhZTM4XHVjNzc0IFdpLCBcdWIxOTJcdWM3NzQgMVx1Yzc3OCBcdWJlNzVcdWM4NzBcdWFjMDFcdWM3NzQgMSB+IE4gXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YjljY1x1YjRlNFx1YzViNFx1YzljMFx1YWNlMCBcdWM3ODhcdWIyZTQuIFx1YjA5OFx1Y2Y1NFx1YjM1NCBcdWQ2OGNcdWM2ZDBcdWI0ZTRcdWM3NDAgXHVjNzc0IFx1YmU3NVx1Yzg3MFx1YWMwMVx1YjRlNFx1Yzc0NCBcdWJhYThcdWI0NTAgXHVjMzEzXHVjNTQ0XHVjMTFjIChcdWJjODRcdWI5YWNcdWJhNzQgXHVjNTQ4XHViNDFjXHViMmU0KSBcdWNlMzVcdWNlMzVcdWM3NzQgXHVjZjAwXHVjNzc0XHVkMDZjXHViOTdjIFx1YjljY1x1YjRlNFx1YWNlMFx1Yzc5MCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Y2YwMFx1Yzc3NFx1ZDA2Y1x1YjI5NCBcdWM1ZWNcdWI3ZWMgXHVjZTM1XHVjNzNjXHViODVjIFx1YWQ2Y1x1YzEzMVx1YjQyMCBcdWMyMTggXHVjNzg4XHViMjk0XHViMzcwLCBcdWQ1NWMgXHVjZTM1XHVjNzU4IFx1YWUzOFx1Yzc3NFx1YjI5NCBcdWFkZjggXHVjZTM1XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWJlNzVcdWM4NzBcdWFjMDFcdWM3NTggXHVhZTM4XHVjNzc0XHVjNzU4IFx1ZDU2OVx1Yzc3NFx1YmE3MCwgXHVjNzA0XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWNlMzVcdWM3NTggXHVhZTM4XHVjNzc0XHVhYzAwIFx1YzU0NFx1Yjc5OFx1YzVkMCBcdWM3ODhcdWIyOTQgXHVjZTM1XHVjNzU4IFx1YWUzOFx1Yzc3NFx1YmNmNFx1YjJlNCBcdWQwNzQgXHVjMjE4IFx1YzVjNlx1YjJlNC4gKFx1YWRmOFx1YjdlY1x1YmE3NCwgXHVjZjAwXHVjNzc1XHVjNzc0IFx1YmIzNFx1YjEwOFx1YzljMFx1YWNlMCBcdWI5ZDAgXHVhYzgzXHVjNzc0XHViMmU0ISk8XC9wPlxyXG5cclxuPHA+XHViNjEwXHVkNTVjLCBcdWIwOThcdWM5MTFcdWM1ZDAgXHViOWNjXHViNGU0XHVjNWI0XHVjOWM0IFx1YmU3NVx1Yzg3MFx1YWMwMVx1Yzc0MCBcdWM4MDRcdWM1ZDAgXHViOWNjXHViNGU0XHVjNWI0XHVjOWM0IFx1YmU3NVx1Yzg3MFx1YWMwMVx1YmNmNFx1YjJlNCBcdWIwYWVcdWM3NDAgXHVjZTM1XHVjNWQwIFx1YzYyY1x1Yjc3Y1x1YWMwOCBcdWMyMTggXHVjNWM2XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWI5N2MgXHViOWNjXHVjODcxXHVkNTU4XHViMjk0IFx1YzEyMFx1YzVkMFx1YzExYyBcdWNkNWNcdWIzMDBcdWQ1NWNcdWM3NTggXHViMTkyXHVjNzc0XHViODVjIFx1Y2YwMFx1Yzc3NVx1Yzc0NCBcdWMzMTNcdWFjZTBcdWM3OTAgXHVkNTYwXHViNTRjLCBcdWFjZmNcdWM1ZjAgXHViYTg3XHVjZTM1XHVhZTRjXHVjOWMwIFx1YzMxM1x1Yzc0NCBcdWMyMTggXHVjNzg4XHVjNzQ0XHVhZTRjPzxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmx0Oz0gTiAmbHQ7PSAxMDAwMDApPFwvcD5cclxuXHJcbjxwPlx1Yzc3NFx1ZDZjNCBOXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBXaVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQgKDEgJmx0Oz0gV2kgJmx0Oz0gMTAwMDApPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAwXHVjN2E1IFx1YjE5Mlx1Yzc0MCBcdWNmMDBcdWM3NzRcdWQwNmNcdWM3NTggXHVkMDZjXHVhZTMwXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1Yjc3Yy48XC9wPlxyXG4iLCJoaW50IjoiPHA+XHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWFkNmNcdWMxMzFcdWM3NzQgXHVhYzAwXHViMmE1XHVkNTU4XHViMmU0LjxcL3A+XHJcblxyXG48cHJlPlxyXG4gKy0tLS0tLS0tLS0rXHJcbiB8ICAgIDMgICAgIHwgXHJcbiArLS0tKy0tLS0tLSsgXHJcbiB8IDEgfCAgIDIgIHwgXHJcbiArLS0tKy0tLS0tLStcclxuPFwvcHJlPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjYxMTYiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJUb3dlciBvZiBIYXkiLCJkZXNjcmlwdGlvbiI6IjxwPkNvd3Mgc28gaGF0ZSB0aGUgZGFyay4gSW4gb3JkZXIgdG8gY2hhbmdlIGEgbGlnaHRidWxiIGF0IHRoZSB0b3Agb2YgdGhlIGJhcm4sIEJlc3NpZSBtdXN0IGJ1aWxkIGEgdG93ZXIgb3V0IG9mIGJhbGVzIG9mIGhheSB0byBjbGltYiBzbyB0aGF0IHNoZSBjYW4gcmVhY2ggaXQuIFRoZSBOICgxICZsdDs9IE4gJmx0Oz0gMTAwLDAwMCkgYmFsZXMgb2YgaGF5IChjb252ZW5pZW50bHkgbnVtYmVyZWQgMS4uTikgZW50ZXIgdGhlIGJhcm4gc2VxdWVudGlhbGx5IG9uIGEgY29udmV5b3IgYmVsdC4gQmFsZSBpIGhhcyBpbnRlZ2VyIHdpZHRoIHdfaSAoMSAmbHQ7PSB3X2kgJmx0Oz0gMTAsMDAwKTsgYWxsIGJhbGVzIGhhdmUgZGVwdGggYW5kIGhlaWdodCBvZiBvbmUgdW5pdC48XC9wPlxyXG5cclxuPHA+QmVzc2llIG11c3QgdXNlIGFsbCBOIGhheSBiYWxlcyB0byBidWlsZCB0aGUgdG93ZXIgYW5kIG11c3QgbGF5IHRoZW0gZG93biBpbiB0aGUgb3JkZXIgdGhleSBhcnJpdmUuIFNoZSBjYW4gbGF5IGFzIG1hbnkgYmFsZXMgYXMgc2hlIHdpc2hlcyAodGlnaHRseSBwYWNrZWQgaW4gYSBsaW5lLCBvZiBjb3Vyc2UpIHRvIGNyZWF0ZSB0aGUgZm91bmRhdGlvbiBvZiB0aGUgdG93ZXIuIFNoZSBjYW4gdGhlbiBsYXkgc29tZSBvZiB0aGUgbmV4dCBiYWxlcyBvbiB0b3Agb2YgdGhlIHByZXZpb3VzIGxldmVsIHRvIGNyZWF0ZSB0aGUgbmV4dCBsZXZlbCAobm8gbGV2ZWwgY2FuIGJlIHdpZGVyIHRoYW4gdGhlIGxldmVsIGJlbmVhdGggaXQpLiBTaGUgY29udGludWVzIHRoaXMgcHJvY2VzcyB1bnRpbCBhbGwgdGhlIGJhbGVzIGFyZSB1c2VkLiBTaGUgbXVzdCBzdGFjayB0aGUgYmFsZXMgaW4gdGhlIG9yZGVyIHRoZXkgYXJyaXZlLCBmcm9tIHRoZSBib3R0b20gdG8gdGhlIHRvcCBvZiB0aGUgdG93ZXIuIFRvIGJlIGNsZWFyOiBzaGUgbXVzdCBub3QgdHJ5IHRvIHNuZWFrIGEgYmFsZSBiYWNrIG9uIHRoZSBmb3VuZGF0aW9uIGFmdGVyIGEgYmFsZSBpcyBwbGFjZWQgb24gdGhlIHNlY29uZCBsYXllci48XC9wPlxyXG5cclxuPHA+QmVzc2llJiMzOTtzIGdvYWwgaXMgdG8gY3JlYXRlIHRoZSB0YWxsZXN0IHRvd2VyIHBvc3NpYmxlIC0tIGFuZCBzaGUgYWxyZWFkeSBrbm93cyBob3cgd2lkZSBlYWNoIGV2ZXJ5IGJhbGUgb2YgaGF5IHdpbGwgYmUgYXMgaXQgY29tZXMgaW50byB0aGUgYmFybiBvbiB0aGUgYmVsdC4gSG93IHRhbGwgYSB0b3dlciBjYW4gc2hlIGNvbnN0cnVjdD88XC9wPlxyXG4iLCJpbnB1dCI6Ijx1bD5cclxuXHQ8bGk+TGluZSAxOiBBIHNpbmdsZSBpbnRlZ2VyOiBOPFwvbGk+XHJcblx0PGxpPkxpbmVzIDIuLk4rMTogTGluZSBpKzEgY29udGFpbnMgYSBzaW5nbGUgaW50ZWdlcjogd19pPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHVsPlxyXG5cdDxsaT5MaW5lIDE6IEEgc2luZ2xlIGludGVnZXIsIHRoZSBoZWlnaHQgb2YgdGhlIHRhbGxlc3QgcG9zc2libGUgdG93ZXIgdGhhdCBjYW4gYmUgYnVpbHQ8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiPHA+VXNlIHRoZSBmaXJzdCBiYWxlcyB3aXRoIHdpZHRoIDEgYW5kIDIgZm9yIHRoZSBib3R0b20gcm93ICh0b3RhbCB3aWR0aDogMyksIHRoZW4gdGhlIG5leHQgYmFsZSAod2lkdGggMykgZm9yIHRoZSB0b3Agcm93OjxcL3A+XHJcblxyXG48cHJlPlxyXG4gICAgICAgICAgICArLS0tLS0tLS0tLStcclxuICAgICAgICAgICAgfCAgICAzICAgICB8XHJcbiAgICAgICAgICAgICstLS0rLS0tLS0tK1xyXG4gICAgICAgICAgICB8IDEgfCAgIDIgIHxcclxuICAgICAgICAgICAgKy0tLSstLS0tLS0rPFwvcHJlPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==