You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

出题人

软工222陈冠霖

题目

小津经营着一家面包店，每天都要进货和售卖面包。小津每天都会记录自己的收入和支出，以便更好地管理自己的财务状况。 用一个数组arr来同时表示每天面包的进价和卖出价，数组的第 i 个元素表示第 i 天的价格。为了节约粮食，小津必须将买进的面包卖出后才能继续进货。小津最多可以进行两次交易，求小津可以获得的最大利润。 注：买进面包再卖出之后才算一次交易。

输入格式

输入一个正整数 n 表示数组的长度，再输入 n 个正整数表示数组的元素。

输出格式

输出一个正整数表示小津可以获得的最大利润。

样例 #1

样例输入 #1

8
3 3 5 0 0 3 1 4

样例输出 #1

6

解释： 在第 4 天（面包价格 = 0）的时候买入，在第 6 天（面包价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。 随后，在第 7 天（面包价格 = 1）的时候买入，在第 8 天 （面包价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。

提示

1 <= n <= 10^5 1 <= arr[i] <= 10^9