问题 B: 股票难题（加强）

问题 B: 股票难题（加强）

时间限制: 1 Sec  内存限制: 256 MB
提交: 24  解决: 7
[提交][状态][讨论版][命题人:]

题目描述

这些日子乔治一直在研究股票，经过调研，他终于发现了某公司股票的规 律。更可喜的是，乔治能推算出这家公司每天的股价，为了防止别人发现他的秘密，他决定对于这家公司的股票最多买入、卖出各一次。同时，由于乔治有前科，交易所只允许乔治在第X天开始才能购买和出售股票。请问乔治如果在第X天开始购买股票，他能赚取的最多的钱是多少？（乔治可以不买）

输入

第一行，一个正整数 n，表示天数； 

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

第三行，测试组数q。

接下来q行，每行一个整数X,表示乔治可以在第X天购买和出售股票。

输出

一共q行，表示如果从X天购买股票，乔治可以赚取的最大钱数。

样例输入

5
1 2 5 4 3
3
1
2
3

样例输出

4
3
0

提示


对于 100%的数据：1<=n<=10^5,1<=q<=10^5 1<=X<=n 股票价格不超过 1000000000

[提交][状态]