题目描述

小珊用时针模拟时间旅行的时候，发现自己真的能进行时间旅行了（做梦中？）。她学校有个跳蚤市场，同学们都拿一些闲置物品在这个市场上买卖。小珊提前获取了一份商品连续几天的价格，请问，小珊只买卖一次情况下，她最多能赚多少钱？

输入格式

第一行只有一个整数 n，表示记录商品价格的天数。

第二行有 n 个整数 $a_i$, 依次表示第 i 天中商品的价格。

数据规模

50% 的数据中，1 ≤ n , $a_i$ ≤ 1000

100% 的数据中，1 ≤ n , $a_i$ ≤ 100000

输出格式

输出只有一行，一个整数，表示一次买卖最多赚多少钱。

样例

4
947 267 359 771

504

样例说明

第 2 天花 267 元买入，第 4 天 771 元时卖出，最多赚 504 元。