题目描述

给定一个整数 $n$，以及一个长度为 $n$ 的数组 $prices$，其中 $prices_i$ 表示某支股票第 $i$ 天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候最多只能持有一股股票。你也可以先购买，然后在同一天出售。

输出你能获得的最大利润。

输入格式

第一行输入一个整数 $n$，表示数组长度。

第二行输入 $n$ 个整数，表示股票每天的价格。

输出格式

输出一个整数，表示你能获得的最大利润。

样例

6 
7 1 5 3 6 4

7

5
5 4 3 2 1

0

样例解释

对于样例 $1$，在第 $2$ 天（股票价格为 $1$）买入，在第 $3$ 天（股票价格为 $5$）卖出，这笔交易可以获得利润 $5 - 1 = 4$。

随后，在第 $4$ 天（股票价格为 $3$）买入，在第 $5$ 天（股票价格为 $6$）卖出，这笔交易可以获得利润 $6 - 3 = 3$。

总利润为 $4 + 3 = 7$。

数据范围

$1 \le n \le 3 \times 10^4$。

$0 \le prices_i \le 10^4$。