1874: Stock Exchange(Hard Version)
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：194
解决：75
题目描述
（简单版和困难版的不同在于n的数据范围。在此版本中 1≤n≤10⁶，对时间复杂度的要求更高）
zhz具有一种神奇的预言未来的能力，于是他决定来炒股，已知某支股票未来n天的价格，zhz只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。请你帮助zhz思考怎样买入卖出才能赚的最多。
输入
共有两行：
(1) 第一行包含一个整数 n（1 ≤ n ≤ 10⁶）；
(2) 第二行包含n个正整数，其中第i个正整数表示的是该股票在第i天的价值（保证在int范围内）；
输出
输出一个整数，表示zhz可以从这笔交易中获取的最大利润。如果不能获取任何利润，返回 0 。
样例输入 复制
7
3 7 1 2 5 6 4样例输出 复制
5提示
第三天股票价值为1的时候买入，在第六天股票价值为6的时候卖出。