按时买卖

题目描述

同一种纪念品连续N天的价格按时间给出。你可以不交易，或选择某一天买入一件、之后的某一天卖出；必须先买后卖，不能同一天买卖，也不能交易多次。求最大非负利润。

输入格式

第一行整数N；第二行依次给出N个整数。

输出格式

输出最大利润；没有获利机会输出0。

样例 1

输入

5
7 5 9 4 8

输出

4

说明

第2天买第3天卖，或第4天买第5天卖。

样例 2

输入

3
9 5 2

输出

0

说明

选择不交易。

数据范围

• 1≤N≤100000。
• 每个整数在0至1000000000之间，允许重复；输入顺序为题目中的原始顺序。