SPOJ in Armenian

Կոնյակի գործարանում ցանկանում են պլանավորել կոնյակի արտադրություն։ Ամեն օր ճիշտ մեկ տակառ պետք է լցվի կոնյակով։ Յուրաքանչյուր տակառ որոշակի քանակությամբ օրեր հետո պետք է բացվի։ Այդ թիվը փակցվում է տակառի վրա։ Յուրաքանչյուր տակառ միայն մեկ անգամ է օգտագործվում։ Հարկավոր է գրել ծրագիր, որը հաշվի, թե տակառներում կոնյակ լցնելու պլանավորումը ճիշտ կազմակերպելու դեպքում վերջին տակառը ամենաշուտը քանի օր հետո կբացվի։

Մուտք

Առաջին տողում տրված է տակառների N (1 ≤ N ≤ 100000) քանակը։ Հաջորդ տողում տրված են N հատ թվեր, որոնցից i-րդը ցույց է տալիս, թե i-րդ տակառում կոնյակը քանի օր պետք է մնա մինչև բացելը։ Այդ թվերը դրական ամբողջ թվեր են և չեն գերազանցում 1000000-ը։

Ելք

Պետք է արտածել մեկ թիվ, որը պետք է ցույց տա, թե առաջին տակառը փակելուց հետո մինիմումը քանի օր անց պետք է բացել վերջին տակառը։

օրինակներ

Input:
4
2 3 4 3

Output:
6

Input:
6
39 19 38 39 22 35

Output:
41