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

Description

这些日子乔治一直在研究股票，经过调研，他终于发现了某公司股票的规律。更可喜的是，乔治能推算出这家公司每天的股价，为了防止别人发现他的秘密，他决定对于这家公司的股票最多买入、卖出各一次。现在他已经将股票 价格列了出来，根据股票价格表，你能算出乔治的每股股票最多能赚多少钱吗？ 【样例说明】 第 2 天买入，第 4 天卖出，赚得 771-267=504。

【数据范围】 对于 30%的数据：n<=1000； 对于 60%的数据：n<=10000； 对于 100%的数据：n<=1000000； 对于 100%的数据：股票价格不超过 1000000000。

Format

Input

第一行，一个正整数 n，表示天数； 第二行，用空格隔开的 n 个正整数，依次表示 n 天中每股股票的价格。

Output

输出只有一行，一个整数，表示每股最多赚多少钱。

Samples

4 

947 267 359 771

504

Limitation

1s, 1024KiB for each test case.