시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 116 26 20 32.787%

문제

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

케이크를 만들기 위해서 현재 길이 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+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsdDs9IE4gJmx0Oz0gMTAwMDAwKTxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWQ2YzQgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgV2lcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0ICgxICZsdDs9IFdpICZsdDs9IDEwMDAwKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMFx1YzdhNSBcdWIxOTJcdWM3NDAgXHVjZjAwXHVjNzc0XHVkMDZjXHVjNzU4IFx1ZDA2Y1x1YWUzMFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWI3N2MuPFwvcD5cclxuIiwiaGludCI6IjxwPlx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NDAgXHVhZDZjXHVjMTMxXHVjNzc0IFx1YWMwMFx1YjJhNVx1ZDU1OFx1YjJlNC48XC9wPlxyXG5cclxuPHByZT5cclxuICstLS0tLS0tLS0tK1xyXG4gfCAgICAzICAgICB8IFxyXG4gKy0tLSstLS0tLS0rIFxyXG4gfCAxIHwgICAyICB8IFxyXG4gKy0tLSstLS0tLS0rXHJcbjxcL3ByZT5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI2MTE2IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiVG93ZXIgb2YgSGF5IiwiZGVzY3JpcHRpb24iOiI8cD5Db3dzIHNvIGhhdGUgdGhlIGRhcmsuIEluIG9yZGVyIHRvIGNoYW5nZSBhIGxpZ2h0YnVsYiBhdCB0aGUgdG9wIG9mIHRoZSBiYXJuLCBCZXNzaWUgbXVzdCBidWlsZCBhIHRvd2VyIG91dCBvZiBiYWxlcyBvZiBoYXkgdG8gY2xpbWIgc28gdGhhdCBzaGUgY2FuIHJlYWNoIGl0LiBUaGUgTiAoMSAmbHQ7PSBOICZsdDs9IDEwMCwwMDApIGJhbGVzIG9mIGhheSAoY29udmVuaWVudGx5IG51bWJlcmVkIDEuLk4pIGVudGVyIHRoZSBiYXJuIHNlcXVlbnRpYWxseSBvbiBhIGNvbnZleW9yIGJlbHQuIEJhbGUgaSBoYXMgaW50ZWdlciB3aWR0aCB3X2kgKDEgJmx0Oz0gd19pICZsdDs9IDEwLDAwMCk7IGFsbCBiYWxlcyBoYXZlIGRlcHRoIGFuZCBoZWlnaHQgb2Ygb25lIHVuaXQuPFwvcD5cclxuXHJcbjxwPkJlc3NpZSBtdXN0IHVzZSBhbGwgTiBoYXkgYmFsZXMgdG8gYnVpbGQgdGhlIHRvd2VyIGFuZCBtdXN0IGxheSB0aGVtIGRvd24gaW4gdGhlIG9yZGVyIHRoZXkgYXJyaXZlLiBTaGUgY2FuIGxheSBhcyBtYW55IGJhbGVzIGFzIHNoZSB3aXNoZXMgKHRpZ2h0bHkgcGFja2VkIGluIGEgbGluZSwgb2YgY291cnNlKSB0byBjcmVhdGUgdGhlIGZvdW5kYXRpb24gb2YgdGhlIHRvd2VyLiBTaGUgY2FuIHRoZW4gbGF5IHNvbWUgb2YgdGhlIG5leHQgYmFsZXMgb24gdG9wIG9mIHRoZSBwcmV2aW91cyBsZXZlbCB0byBjcmVhdGUgdGhlIG5leHQgbGV2ZWwgKG5vIGxldmVsIGNhbiBiZSB3aWRlciB0aGFuIHRoZSBsZXZlbCBiZW5lYXRoIGl0KS4gU2hlIGNvbnRpbnVlcyB0aGlzIHByb2Nlc3MgdW50aWwgYWxsIHRoZSBiYWxlcyBhcmUgdXNlZC4gU2hlIG11c3Qgc3RhY2sgdGhlIGJhbGVzIGluIHRoZSBvcmRlciB0aGV5IGFycml2ZSwgZnJvbSB0aGUgYm90dG9tIHRvIHRoZSB0b3Agb2YgdGhlIHRvd2VyLiBUbyBiZSBjbGVhcjogc2hlIG11c3Qgbm90IHRyeSB0byBzbmVhayBhIGJhbGUgYmFjayBvbiB0aGUgZm91bmRhdGlvbiBhZnRlciBhIGJhbGUgaXMgcGxhY2VkIG9uIHRoZSBzZWNvbmQgbGF5ZXIuPFwvcD5cclxuXHJcbjxwPkJlc3NpZSYjMzk7cyBnb2FsIGlzIHRvIGNyZWF0ZSB0aGUgdGFsbGVzdCB0b3dlciBwb3NzaWJsZSAtLSBhbmQgc2hlIGFscmVhZHkga25vd3MgaG93IHdpZGUgZWFjaCBldmVyeSBiYWxlIG9mIGhheSB3aWxsIGJlIGFzIGl0IGNvbWVzIGludG8gdGhlIGJhcm4gb24gdGhlIGJlbHQuIEhvdyB0YWxsIGEgdG93ZXIgY2FuIHNoZSBjb25zdHJ1Y3Q/PFwvcD5cclxuIiwiaW5wdXQiOiI8dWw+XHJcblx0PGxpPkxpbmUgMTogQSBzaW5nbGUgaW50ZWdlcjogTjxcL2xpPlxyXG5cdDxsaT5MaW5lcyAyLi5OKzE6IExpbmUgaSsxIGNvbnRhaW5zIGEgc2luZ2xlIGludGVnZXI6IHdfaTxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6Ijx1bD5cclxuXHQ8bGk+TGluZSAxOiBBIHNpbmdsZSBpbnRlZ2VyLCB0aGUgaGVpZ2h0IG9mIHRoZSB0YWxsZXN0IHBvc3NpYmxlIHRvd2VyIHRoYXQgY2FuIGJlIGJ1aWx0PFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IjxwPlVzZSB0aGUgZmlyc3QgYmFsZXMgd2l0aCB3aWR0aCAxIGFuZCAyIGZvciB0aGUgYm90dG9tIHJvdyAodG90YWwgd2lkdGg6IDMpLCB0aGVuIHRoZSBuZXh0IGJhbGUgKHdpZHRoIDMpIGZvciB0aGUgdG9wIHJvdzo8XC9wPlxyXG5cclxuPHByZT5cclxuICAgICAgICAgICAgKy0tLS0tLS0tLS0rXHJcbiAgICAgICAgICAgIHwgICAgMyAgICAgfFxyXG4gICAgICAgICAgICArLS0tKy0tLS0tLStcclxuICAgICAgICAgICAgfCAxIHwgICAyICB8XHJcbiAgICAgICAgICAgICstLS0rLS0tLS0tKzxcL3ByZT5cclxuIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=