传统题 1000ms 256MiB

(改自CSP-X)纪念品

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

小图很喜欢旅游,这次他旅游的国家有 nn 个城市,编号依次为 11nn,并且小图打算从 11 号城市开始按编号依次旅游完所有城市,并且他不会返回已经去过的城市,即每个城市仅走一次。 小图在做旅游攻略时发现,每座城市都有一件相同的纪念品,但是他们的价格可能不一样,所以小图想在某一个城市买入一个纪念品,并在之后的城市中卖掉它,并且小图最少且仅会买入一次卖出一次,这样他就能赚取到其中的差价;于是小图想让你帮他计算一下他最多能赚多少钱,如果亏钱也请告诉他最少亏多少(他只是好奇)。

输入格式

第一行一个整数 nn,表示城市的数量。

第二行有用空格隔开的 nn 个整数,第 ii 个数字 aia_i 表示编号为 ii 的城市的纪念品价格。

对于 30% 的测试数据 2n1031ai1052 \leq n \leq 10^3,1 \leq a_i \leq 10^5

对于 100% 的测试数据 2n1061ai1092 \leq n \leq 10^6,1 \leq a_i \leq 10^9

输出格式

输出一个整数表示小图最多能赚多少钱(亏钱则输出负数)。

样例

5
2 1 6 8 4
7
6
10 8 7 5 3 1
-1

普通练习

未参加
状态
已结束
规则
OI
题目
11
开始于
2024-3-9 23:00
结束于
2024-3-9 23:30
持续时间
1 小时
主持人
参赛人数
1