题目描述

小蓝正在研究股票市场，他希望从股票交易中获得最大利润。

给定一个长度为 $N$ 的整数数组 $A_{1}, A_{2}, \cdots A_{N}$，其中 $A_i$ 表示一支股票在第 $i$ 天的价格。小蓝希望知道他最多完成两笔交易能够获得的最大利润是多少？

注意：小蓝不能同时参与多笔交易（他必须在再次购买前出售掉之前的股票）。

输入描述

第一行包含一个整数 $N$，代表数组长度。

第二行包含 $N$ 个整数 $A_1, A_2, \cdots, A_N$，其中 $A_i$ 表示股票在第 $i$ 天的价格。

输出描述

输出一行包含一个整数表示最大利润。

样例

8
3 3 5 0 0 3 1 4

6

样例1解释

在第 $4$ 天（股票价格 $= 0$）的时候买入，在第 $6$ 天（股票价格 $= 3$）的时候卖出，利润为 $3$。

随后，在第 $7$ 天（股票价格 $= 1$）的时候买入，在第 $8$ 天（股票价格 $= 4$）的时候卖出，利润为 $3$。

总共利润为 $6$。

数据范围

对于所有评测用例，$1 \leq N \leq 10^{5}$，$0 \leq A_i \leq 10^{5}$。