ワイン生産
あなたはワイン生産工場の物流を担当しています。コンテナは
n 個あり、毎日 1つ のコンテナがワインで満たされます。各コンテナについて、開封する前に閉じたままでいなければならない日数が分かっています。すべてのコンテナを開封し終えるまでに要する時間を最小限に抑えたいと考えています。入力
入力の最初の行には整数
n (1 ≤ n ≤ ) が1つ与えられます。次の行には、空白区切りの
n 個の整数 (1 ≤ ≤ ) が与えられ、これは各コンテナが開封可能になるまで閉じたままにしておく必要がある日数を表します。出力
すべてのコンテナを開けることができるようになるまでに待たなければならない最短の時間を出力してください。
Examples
Input | Output |
4
2 3 4 3 | 6 |
6
39 19 38 39 22 35 | 41 |
Explanation
- Example 1 (箇条書きの番号は日数を表します):
- Fill the container that needs to be kept closed for 4 days
- Fill the container that needs to be kept closed for 3 days
- Fill the container that needs to be kept closed for 3 days
- Fill the container that needs to be kept closed for 2 days
- Open the containers filled during Day 1 and Day 2
- Open the containers filled during Day 3 and Day 4 ⇒ all are open
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB