题目描述

给定一个包含n个正整数的数组a，其中a[i] 表示第 i 天的一支股票价格 。​

设计一个算法计算出n天对一支股票进行买卖操作能够获得的最大利润。

注意： 每天只能进行一次买入/卖出股票。 股票交易有1天冷冻期 (如果当天把股票卖出则无法在第二天买入股票 ，需要在第三天及以后才能再次购买股票)。你不能同时参与多笔交易（你每次只能购买一支股票，若当前已经买入了股票，则在把股票出售前不能再购买股票）。

输入格式

第 1 行包含一个正整数 n。 第 2 行包含n个整数a[i] ，表示第 i 天的股票价格。

输出格式

仅一行，1个整数，表示n天最大利润。

样例1

1
1

0

样例2

5
1 2 3 0 2

3

数据范围

1 ≤ n ≤ 10000； 1 ≤ a[i] ≤ 10000。