题目描述

小珊提前获取了一份商品连续几天的价格，她计划最多只进行一次买卖（先买入再卖出），请问这种情况下她最多能赚多少钱？

输入格式

1. 第一行：一个整数n，表示记录商品价格的天数。
2. 第二行：n个整数ai，依次表示第i天商品的价格。

输出格式

一行：一个整数，表示一次买卖能获得的最大利润。

输入输出样例

样例 1

输入

4
947 267 359 771

输出

504

解释

第2天以267元买入，第4天以771元卖出，利润为771-267=504元，此为最大利润。

数据规模

• 50%的数据：1≤n, ai≤1000
• 100%的数据：1≤n, ai≤100000