Բաժնետոմսերի առք ու վաճառք
Ձեզ տրված են
n ամբողջ թվեր, որոնք ներկայացնում են ձեր ամենասիրած ընկերության բաժնետոմսերի արժեքները: Դուք ցանկանում եք որոշել, թե երբ ավելի եկամտաբեր կլինի գնել և վաճառել բաժնետոմսերը: Առքն ու վաճառքը պետք է իրականացվի միայն մեկ անգամ: Ձեր նպատակն է ստանալ առավելագույն շահույթ (գնել էժան և վաճառել թանկ):Հաշվեք, թե ամենաշատը որքան շահույթ կարող եք ստանալ ձեր սիրելի ընկերության բաժնետոմսերից, իսկ եթե շահույթ ստանալ չի ստացվում, ծրագիրը պետք է տպի 0 (այսինքն բաժնետոմս չեք գնի-վաճառի):
Մուտք
Մուտքի առաջին տողում տրված է մեկ ամբողջ թիվ
n (1 ≤ n ≤ ):Մուտքի հաջորդ տողում տրված են բացատով բաժանված արժեքները, որոնք ներկայացնում են բաժնետոմսերի գները (0 ≤ ≤ 1000):
Ելք
Ծրագիրը պետք է տպի բաժնետոմսերը մեկ անգամ գնելով և մեկ անգամ վաճառելով ստացվող առավելագույն շահույթը:
Օրինակներ
Մուտք | Ելք |
5
4 2 6 8 1 | 6 |
4
8 6 4 3 | 0 |
Պարզաբանում
- Գնումը կատարվում է, երբ բաժնետոմսի արժեքը 2 է, իսկ վաճառքը՝ երբ այն 8 է:
- Այս դեպքում շահույթ ստանալ հնարավոր չէ, քանի որ գինը շարունակաբար իջնում է:
Հուշում
Յուրաքանչյուր քայլում կարող եք պահել այդ պահի «լավագույն» արդյունքը և միևնույն ժամանակ հիշել բաժնետոմսի մինչ այդ պահը գրանցված նվազագույն արժեքը:
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB