1839：区间最大值
文件提交：无需freopen
内存限制：128 MB
时间限制：1.000 S
评测方式：普通裁判
命题人：
提交：3
解决：2
题目描述
对于数列 $a$，定义区间 $[l,r]$ 的分值为 $\sum\limits_{i=l}^r a_i^2-\sum\limits_{i=l}^r a_i-k\times (r-l+1)$。其中 $k$ 是一个给定的参数。
你获得了一个很短的数列，希望找到一个分值最大的区间，这个问题你可以轻松解决，你可以把所有的区间以及它们的分值都找了出来。
但是不服输的小蒜想要挑战你，因此他给了你一个很长的数列，你还能找到**所有非空区间的分值的最大值**吗？
> 提示：$\sum\limits_{i=l}^r a_i = a_{l} + a_{l + 1} + a_{l + 2} + \cdots + a_{r}$
形式化题意：
给定 $n,k$ 和序列 $\{a_n\}$，试求 $\max\limits_{1\leq l\leq r\leq n}\{\sum\limits_{i=l}^r a_i^2-\sum\limits_{i=l}^r a_i-k\times (r-l+1)\}$ 的结果。
你获得了一个很短的数列，希望找到一个分值最大的区间，这个问题你可以轻松解决，你可以把所有的区间以及它们的分值都找了出来。
但是不服输的小蒜想要挑战你，因此他给了你一个很长的数列，你还能找到**所有非空区间的分值的最大值**吗？
> 提示：$\sum\limits_{i=l}^r a_i = a_{l} + a_{l + 1} + a_{l + 2} + \cdots + a_{r}$
形式化题意：
给定 $n,k$ 和序列 $\{a_n\}$，试求 $\max\limits_{1\leq l\leq r\leq n}\{\sum\limits_{i=l}^r a_i^2-\sum\limits_{i=l}^r a_i-k\times (r-l+1)\}$ 的结果。
输入
第一行两个正整数，分别表示 $n,k$。
接下来一行 $n$ 个正整数，表示数列 $a$。
变量含义如上述所示。
对于 $100\%$ 的数据，$1\le n\le 10^6,0 \leq a_i \leq 10^6, 0\le k\le 10^9$。
接下来一行 $n$ 个正整数，表示数列 $a$。
变量含义如上述所示。
对于 $100\%$ 的数据，$1\le n\le 10^6,0 \leq a_i \leq 10^6, 0\le k\le 10^9$。
输出
输出一个整数，表示答案。
样例输入-1 复制
6 0
1 2 3 4 5 6样例输出-1 复制
70样例输入-2 复制
1 1234
10样例输出-2 复制
-1144提示
样例解释1：
假如选择了区间 $[1,2]$，分值是 $1^2 + 2^2 - (1+2) - 2\times k = 2$
假如选择了区间 $[1,6]$, 分值是 $1^2 + 2^2 + 3^3 + 4^2 + 5^2 + 6^2 - (1+2+3+4+5+6) - 6\times k = 70$
可以证明，不存在分值大于 $70$ 的区间，因此答案就是 $70$。
解题思路：
