Вы можете идеально предсказать цену определенной акции на следующие N дней. Вы хотите заработать на этом знании, но хотите продавать или покупать не больше одной акции в день. Другими словами, каждый день вы будете либо покупать одну акцию, либо продавать одну акцию, либо ничего не делать. Изначально у вас нет акций, и вы не можете продать акцию, когда у вас их нет. В конце N дней вы хотите опять остаться без акций, но хотите заработать как можно больше.
Выходные данные
Выведите максимальную сумму, которую вы можете заработать к концу N дней.
Примечание
В первом примере купите акцию за 5, еще одну за 4, продайте за 9 и другую за 12. Затем купите за 2 и продайте за 10. В итоге получите - 5 - 4 + 9 + 12 - 2 + 10 = 20.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
9
10 5 4 7 9 12 6 2 10
|
20
|
|
2
|
20
3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4
|
41
|