Դարձնել չնվազող
Տրված է
n ամբողջ թվերից բաղկացած զանգված. Ձեզ խնդրում են այն փոխակերպել այնպես, որ տարրերն դասավորված լինեն չնվազող կարգով: Թույլատրվում է զանգվածի ցանկացած տարրին մի քանի անգամ գումարել 1, ընդ որում յուրաքանչյուր անգամ 1 գումարելու համար վճարում եք $1: Պետք է հասնել չնվազող հաջորդականության հնարավոր ամենափոքր գումարով: Հաշվեք, թե ի վերջո նվազագույն ինչ գումար կպահանջվի այդ փոխակերպման համար:Մուտք
Մուտքի առաջին տողում գրված է
n ամբողջ թիվը (2 ≤ n ≤ ), որն արտացոլում է զանգվածի էլեմենտների քանակը:Մուտքի երկրորդ տողում տրված են
n ամբողջ թվեր ( ≤ ≤ ), որոնք զանգվածի էլեմենտներն են:Ելք
Ծրագիրը պետք է տպի այն նվազագույն գումարը, որը պահանջվում է զանգվածը չնվազող հաջորդականություն դարձնելու համար:
Օրինակներ
Մուտք | Ելք |
4
-2 3 1 0 | 5 |
5
1 2 3 4 4 | 0 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB