시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 834 517 455 66.230%

문제

농부 상근이는 마당에 심기 위한 나무 묘목 n개를 구입했다. 묘목 하나를 심는데 걸리는 시간은 1일이고, 상근이는 각 묘목이 다 자라는데 몇 일이 걸리는지 정확하게 알고 있다.

상근이는 마을 이장님을 초대해 자신이 심은 나무를 자랑하려고 한다. 이장님을 실망시키면 안되기 때문에, 모든 나무가 완전히 자란 이후에 이장님을 초대하려고 한다. 즉, 마지막 나무가 다 자란 다음날 이장님을 초대할 것이다.

상근이는 나무를 심는 순서를 신중하게 골라 이장님을 최대한 빨리 초대하려고 한다. 이장님을 몇 일에 초대할 수 있을까?

입력

입력은 두 줄로 이루어져 있다. 첫째 줄에는 묘목의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄에는 각 나무가 다 자라는데 몇 일이 걸리는지를 나타낸 ti가 주어진다. (1 ≤ ti ≤ 1,000,000)

출력

첫째 줄에 몇 일에 이장님을 초대할 수 있는지 출력한다. 답이 여러가지인 경우에는 가장 작은 값을 출력한다. 묘목을 구입한 날이 1일이다.

예제 입력 1

4
2 3 4 3

예제 출력 1

7

예제 입력 2

6
39 38 9 35 39 20

예제 출력 2

42
W3sicHJvYmxlbV9pZCI6IjkyMzciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM3NzRcdWM3YTVcdWIyZDggXHVjZDA4XHViMzAwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWIxOGRcdWJkODAgXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YjljOFx1YjJmOVx1YzVkMCBcdWMyZWNcdWFlMzAgXHVjNzA0XHVkNTVjIFx1YjA5OFx1YmIzNCBcdWJiMThcdWJhYTkgblx1YWMxY1x1Yjk3YyBcdWFkNmNcdWM3ODVcdWQ1ODhcdWIyZTQuIFx1YmIxOFx1YmFhOSBcdWQ1NThcdWIwOThcdWI5N2MgXHVjMmVjXHViMjk0XHViMzcwIFx1YWM3OFx1YjlhY1x1YjI5NCBcdWMyZGNcdWFjMDRcdWM3NDAgMVx1Yzc3Y1x1Yzc3NFx1YWNlMCwgXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YWMwMSBcdWJiMThcdWJhYTlcdWM3NzQgXHViMmU0IFx1Yzc5MFx1Yjc3Y1x1YjI5NFx1YjM3MCBcdWJhODcgXHVjNzdjXHVjNzc0IFx1YWM3OFx1YjlhY1x1YjI5NFx1YzljMCBcdWM4MTVcdWQ2NTVcdWQ1NThcdWFjOGMgXHVjNTRjXHVhY2UwIFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YjljOFx1Yzc0NCBcdWM3NzRcdWM3YTVcdWIyZDhcdWM3NDQgXHVjZDA4XHViMzAwXHVkNTc0IFx1Yzc5MFx1YzJlMFx1Yzc3NCBcdWMyZWNcdWM3NDAgXHViMDk4XHViYjM0XHViOTdjIFx1Yzc5MFx1Yjc5MVx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1Yzc3NFx1YzdhNVx1YjJkOFx1Yzc0NCBcdWMyZTRcdWI5ZGRcdWMyZGNcdWQwYTRcdWJhNzQgXHVjNTQ4XHViNDE4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgXHViYWE4XHViNGUwIFx1YjA5OFx1YmIzNFx1YWMwMCBcdWM2NDRcdWM4MDRcdWQ3ODggXHVjNzkwXHViNzgwIFx1Yzc3NFx1ZDZjNFx1YzVkMCBcdWM3NzRcdWM3YTVcdWIyZDhcdWM3NDQgXHVjZDA4XHViMzAwXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjOTg5LCBcdWI5YzhcdWM5YzBcdWI5YzkgXHViMDk4XHViYjM0XHVhYzAwIFx1YjJlNCBcdWM3OTBcdWI3ODAgXHViMmU0XHVjNzRjXHViMGEwIFx1Yzc3NFx1YzdhNVx1YjJkOFx1Yzc0NCBcdWNkMDhcdWIzMDBcdWQ1NjAgXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHViMDk4XHViYjM0XHViOTdjIFx1YzJlY1x1YjI5NCBcdWMyMWNcdWMxMWNcdWI5N2MgXHVjMmUwXHVjOTExXHVkNTU4XHVhYzhjIFx1YWNlOFx1Yjc3YyBcdWM3NzRcdWM3YTVcdWIyZDhcdWM3NDQgXHVjZDVjXHViMzAwXHVkNTVjIFx1YmU2OFx1YjlhYyBcdWNkMDhcdWIzMDBcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWM3NzRcdWM3YTVcdWIyZDhcdWM3NDQgXHViYTg3IFx1Yzc3Y1x1YzVkMCBcdWNkMDhcdWIzMDBcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1Yzc0NFx1YWU0Yz88XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWI0NTAgXHVjOTA0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViYjE4XHViYWE5XHVjNzU4IFx1YzIxOCBOICgxICZsZTsgTiAmbGU7IDEwMCwwMDApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjMDEgXHViMDk4XHViYjM0XHVhYzAwIFx1YjJlNCBcdWM3OTBcdWI3N2NcdWIyOTRcdWIzNzAgXHViYTg3IFx1Yzc3Y1x1Yzc3NCBcdWFjNzhcdWI5YWNcdWIyOTRcdWM5YzBcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI4IHQ8c3ViPmk8XC9zdWI+XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyB0PHN1Yj5pPFwvc3ViPiAmbGU7IDEsMDAwLDAwMCk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YmE4NyBcdWM3N2NcdWM1ZDAgXHVjNzc0XHVjN2E1XHViMmQ4XHVjNzQ0IFx1Y2QwOFx1YjMwMFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0XHVjOWMwIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHViMmY1XHVjNzc0IFx1YzVlY1x1YjdlY1x1YWMwMFx1YzljMFx1Yzc3OCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHVhYzAwXHVjN2E1IFx1Yzc5MVx1Yzc0MCBcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWJiMThcdWJhYTlcdWM3NDQgXHVhZDZjXHVjNzg1XHVkNTVjIFx1YjBhMFx1Yzc3NCAxXHVjNzdjXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjkyMzciLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJQbGFudGluZyBUcmVlcyIsImRlc2NyaXB0aW9uIjoiPHA+RmFybWVyIEpvbiBoYXMgcmVjZW50bHkgYm91Z2h0IG4gdHJlZSBzZWVkbGluZ3MgdGhhdCBoZSB3YW50cyB0byBwbGFudCBpbiBoaXMgeWFyZC4gSXQgdGFrZXMgMSBkYXkgZm9yIEpvbiB0byBwbGFudCBhIHNlZWRsaW5nLCBhbmQgZm9yIGVhY2ggdHJlZSBKb24ga25vd3MgZXhhY3RseSBpbiBob3cgbWFueSBkYXlzIGFmdGVyIHBsYW50aW5nIGl0IGdyb3dzIHRvIGZ1bGwgbWF0dXJpdHkuIEpvbiB3b3VsZCBhbHNvIGxpa2UgdG8gdGhyb3cgYSBwYXJ0eSBmb3IgaGlzIGZhcm1lciBmcmllbmRzLCBidXQgaW4gb3JkZXIgdG8gaW1wcmVzcyB0aGVtIGhlIHdvdWxkIGxpa2UgdG8gb3JnYW5pemUgdGhlIHBhcnR5IG9ubHkgYWZ0ZXIgYWxsIHRoZSB0cmVlcyBoYXZlIGdyb3duLiBNb3JlIHByZWNpc2VseSwgdGhlIHBhcnR5IGNhbiBiZSBvcmdhbml6ZWQgYXQgZWFybGllc3Qgb24gdGhlIG5leHQgZGF5IGFmdGVyIHRoZSBsYXN0IHRyZWUgaGFzIGdyb3duIHVwLjxcL3A+XHJcblxyXG48cD5IZWxwIEpvbiB0byBcdWZiMDFuZCBvdXQgd2hlbiBpcyB0aGUgZWFybGllc3QgZGF5IHdoZW4gdGhlIHBhcnR5IGNhbiB0YWtlIHBsYWNlLiBKb24gY2FuIGNob29zZSB0aGUgb3JkZXIgb2YgcGxhbnRpbmcgdGhlIHRyZWVzIGFzIGhlIGxpa2VzLCBzbyBoZSB3YW50cyB0byBwbGFudCB0aGUgdHJlZXMgaW4gc3VjaCBhIHdheSB0aGF0IHRoZSBwYXJ0eSB3aWxsIGJlIGFzIHNvb24gYXMgcG9zc2libGUuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgY29uc2lzdHMgb2YgdHdvIGxpbmVzLiBUaGUgXHVmYjAxcnN0IGxpbmUgY29udGFpbnMgYSBzaW5nbGUgaW50ZWdlciBOICgxICZsZTsgTiAmbGU7IDEwMCAwMDApIGRlbm90aW5nIHRoZSBudW1iZXIgb2Ygc2VlZGxpbmdzLiBUaGVuIGEgbGluZSB3aXRoIE4gaW50ZWdlcnMgdDxzdWI+aTxcL3N1Yj4gZm9sbG93cyAoMSAmbGU7IHQ8c3ViPmk8XC9zdWI+ICZsZTsgMSAwMDAgMDAwKSwgd2hlcmUgdGkgZGVub3RlcyB0aGUgbnVtYmVyIG9mIGRheXMgaXQgdGFrZXMgZm9yIHRoZSBpdGggdHJlZSB0byBncm93LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPllvdSBwcm9ncmFtIHNob3VsZCBvdXRwdXQgZXhhY3RseSBvbmUgbGluZSBjb250YWluaW5nIG9uZSBpbnRlZ2VyLCBkZW5vdGluZyB0aGUgZWFybGllc3QgZGF5IHdoZW4gdGhlIHBhcnR5IGNhbiBiZSBvcmdhbml6ZWQuIFRoZSBkYXlzIGFyZSBudW1iZXJlZCAxLCAyLCAzLCAuLi4gYmVnaW5uaW5nIGZyb20gdGhlIGN1cnJlbnQgbW9tZW50LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==