题目描述

给定一个长度为 $n$ 的数组 $prices$, 其中第 $i$ 个元素 $prices_{i}$ 代表第 $i$ 天的股票价格，在每一天，可以决定是否购买和/或出售股票。在任何时候最多只能持有一股股票。当然也可以先购买，然后在同一天出售。请你计算能够获得的最大利润。

输入格式

第一行输入一个整数 $n$。

第二行输入 $n$ 个整数，其中第 $i$ 个整数代表 $prices_{i}$。

输出格式

输出一个整数表示答案。

样例

6
7 1 5 3 6 4

7

5
1 2 3 4 5

4

样例1解释

样例 $1$ 中可以选择在第 $2$ 天以价格 $1$ 买入，并在第 $3$ 天以价格以价格 $5$ 卖出，然后在第 $4$ 天以价格 $3$ 买入，在第 $5$ 天以价格 $6$ 卖出，获得利润 $7$。

样例2解释

样例 $2$ 中可以选择在第 $1$ 天买入，在第 $5$ 天卖出，获得利润 $4$。

数据范围

对于 $100\%$ 的数据，$1 \leq n \leq 10^5$, $0 \leq prices_{i} \leq 10^4$。