Գինու արտադրություն
Դուք պատասխանատու եք գինու արտադրության գործարանի լոգիստիկ բաժնի համար։ Կա
n տակառ, և ամեն օր դրանցից միայն մեկն է լցվում գինով։ Դուք յուրաքանչյուր տակառի համար գիտեք, թե քանի օր այն պետք է փակ մնա, նախքան բացելը։ Ձեր նպատակն է նվազագույնի հասցնել այն ընդհանուր ժամանակը, որի ավարտին հնարավոր կլինի բացել բոլոր տակառները։Մուտք
Մուտքի առաջին տողում տրված է
n բնական թիվը (1 ≤ n ≤ )։Հաջորդ տողում տրված են
n բնական թվեր (բաժանված բացատներով) (1 ≤ ≤ ), որոնք ցույց են տալիս, թե քանի օր պետք է ամեն տակառ փակ մնա, մինչ բացելը։Ելք
Ծրագիրը պետք է տպի ամենափոքր հնարավոր ժամանակը, որի ընթացքում հնարավոր կլինի բացել բոլոր տակառները։
Օրինակներ
Մուտք | Ելք |
4
2 3 4 3 | 6 |
6
39 19 38 39 22 35 | 41 |
Բացատրություն
- Օրինակ 1 (թվերը ցույց են տալիս օրերի համարները).
- Լցնել այն տակառը, որը պետք է 4 օր փակ մնա
- Լցնել այն տակառը, որը պետք է 3 օր փակ մնա
- Լցնել այն տակառը, որը պետք է 3 օր փակ մնա
- Լցնել այն տակառը, որը պետք է 2 օր փակ մնա
- Բացել առաջին երկու օրերի ընթացքում պահեստավորված տակառները
- Բացել երրորդ և չորրորդ օրերի ընթացքում պահեստավորված տակառները ⇒ բոլոր տակառները կբացվեն
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB