灵药竞拍

题目描述

在魔法都市的拍卖行里，珍稀的“龙息灵药”每天的价格都在剧烈波动。你作为一名精明的商人，想要通过买卖灵药来赚取金币。

已知未来 $n$ 天内，每天灵药的价格为 $a_i$。由于你的魔力有限，你手中最多只能同时持有一瓶灵药。你可以在任何一天买入一瓶灵药，也可以卖出你手中的灵药。

然而，拍卖行有一个特殊的规定：卖出一瓶灵药后，由于需要办理复杂的手续和清空魔力印记，你必须等待一天（即冷冻期）才能再次买入灵药。也就是说，如果你在第 $i$ 天卖出了灵药，那么你最早只能在第 $i+2$ 天再次买入。

你的目标是计算在 $n$ 天结束时，你最多能获得多少金币的利润？

输入格式

第一行包含一个整数 $n$，表示总天数。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示每天灵药的价格。

输出格式

输出一个整数，表示能获得的最大利润。

输入输出样例 #1

输入 #1

5
1 2 3 0 2

输出 #1

3

输入输出样例 #2

输入 #2

1
1

输出 #2

0

数据范围

对于 $60\%$ 的数据，$1 \le n \le 1000$。

对于 $100\%$ 的数据，$1 \le n \le 10^5$，$0 \le a_i \le 10^9$。