题目描述

给定一个长度为 $N$ 的数组，数组中的第 $i$ 个数字表示一个给定股票在第 $i$ 天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成两笔交易。 注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

输入

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

输出

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

8
3 3 5 0 0 3 1 4

6

提示

$1≤N≤10^5$
样例1：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。共得利润 3+3 = 6。