题目描述

给定一个长度为 $N$ 的数组，数组中的第 $i$ 个数字表示一个给定股票在第 $i$ 天的价格。 如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。 注意你不能在买入股票前卖出股票。

输入

第一行包含整数 $N$，表示数组长度。 第二行包含 $N$ 个不大于 $10^9$ 的正整数，表示完整的数组。

输出

输出一个整数，表示最大利润。

6
7 1 5 3 6 4

5

提示

$1≤N≤10^5$