问题 B:最大回撤

文件提交:无需freopen 内存限制:128 MB 时间限制:1.000 S
评测方式:普通裁判 命题人:
提交:2 解决:2

题目描述

在金融市场上,经常需要统计一只股票的最大回撤。最大回撤是指投资者在某天买入,在之后的某天卖出,可能造成的最大亏损,它可以反应一只股票在历史上的最坏表现。

给定一个整数序列 $a_1,a_2,...,a_n$,每个 $a_i$ 表示同一只股票在某一天的价格,请计算这只股票的最大回撤。即寻找两个下标满足 $1\le i\le j\le n$,且 $a_i-a_j$ 最大。

输入

第一行:单个整数表示 $n$

第二行:$n$ 个整数表示 $a_1,a_2,...,a_n$

$1\le n\le 10^5, -10^5\le a_i\le 10^5$

输出

单个整数:表示这只股票的最大回撤,如果价格一直上涨,输出 $0$。

样例输入-1 复制

5
2 3 7 6 1

样例输出-1 复制

6