百度笔试题之数组差值（题目与源码）
*********************************
给定一个长度为n并且只含有非负整数的数组A，显然这个数组一共有n*(n+1)/2个区间（每个区间至少有一个元素）。给定m个查询值K，对于每个查询值K，我们将每个区间最小值与K做“差值”，“差值”的定义如下：
当最小值MINi不小于K时，则“差值”为MINi – K
否则“差值”为0
你的任务是求出对于每个查询值K时，n*(n+1)/2个“差值”的和。
【数据范围】
1 ≤ n, m ≤ 105
0 ≤ Ai, K < 231
输入数据格式
输入文件的第一行为数组大小n，接下来第二行会有n个整数（用空格隔开）
输入文件的第三行为查询次数m，接下来会有m行，每行均为一个查询值K
输出数据格式
对于每个查询，请在一行中输出对这个查询值K，所有n*(n+1)/2个差值的和。
样例
输入：
4
1 3 2 5
2
2
3
输出：
4
2
【样例解释】
数组1 3 2 5的区间有10个，分别为：
[1], [2], [3], [5], [1 3], [3 2], [2 5], [1 3 2], [3 2 5], [1 3 2 5]
这10个区间的最小值分别为：
[1], [2], [3], [5], [1], [2], [2], [1], [2], [1]
则当K = 2时，所求为0+0+1+3+0+0+0+0+0+0 = 4
当K = 3时，所求为0+0+0+2+0+0+0+0+0+0 = 2
