题目描述

给定一支股票接下来 $n$ 天的价格，设计一个算法计算出最大的利润。

每天你可以进行买入或者卖出，或者不进行任何操作，但是需要遵守以下条件：

• 你不能同时参与多笔交易（你必须在再次买入前卖出之前的股票）。
• 卖出股票后，你无法在第二天买入股票（即冷冻期为 $1$ 天）。

输入格式

第一行一个整数 $n$（$1\le n\le10^5$），表示一共有 $n$ 天。

第二行一共有 $n$ 个整数 $a_{i}$（$0\le a_{i}\le10^9$），表示第 $i$ 天的价格。

输出格式

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

说明与提示

第 $1$ 天买入，第 $2$ 天卖出。

第 $3$ 天处于冷冻期，不能买入。

第 $4$ 天买入，第 $5$ 天卖出。

原题勘误：原图将价格下界写为 $1$，但样例包含 $0$。本题统一允许价格为 $0$，交易规则不变。

来源

浩轩OJ 4388 · 原题图片

数据范围与约定

$1\le n\le10^5$，$0\le a_{i}\le10^9$。

可见测试数据

输入数据 1

5
1 2 3 0 2

输出数据 1

3

输入数据 2

5
7 6 5 4 3

输出数据 2

0

输入数据 3

1
0

输出数据 3

0