题目描述

银河系中分布着 $n$ 个空间站，编号从 $1$ 到 $n$。第 $i$ 个空间站的坐标为 $x_i$（保证 $x_1 < x_2 < \dots < x_n$）。

宇航员需要驾驶飞船从空间站 $1$ 出发，最终到达空间站 $n$。为了节省燃料并控制风险，宇航员制定了如下跳跃规则：

1. 每次跳跃只能从编号较小的空间站跳到编号较大的空间站（即若当前在 $i$，下一步必须去 $j > i$）。
2. 设上次停留的空间站为 $p$，当前准备跳往的空间站为 $q$。这次跳跃产生的“风险值”定义为 $(x_q - x_p)^2 + C \cdot (x_q - x_p)$，其中 $C$ 是一个给定的常数。
3. 总风险值是路径上所有跳跃风险值之和。

你的任务是计算从空间站 $1$ 到空间站 $n$ 的最小总风险值。

输入格式

第一行包含两个整数 $n$ 和 $C$，表示空间站的总数和风险参数。 接下来一行包含 $n$ 个整数 $x_1, x_2, \dots, x_n$，表示各空间站的坐标。

输出格式

输出一行一个整数，表示最小总风险值。

样例

3 0
0 2 5

13

样例解释

$f[1]=0$

$f[2] = (2-0)^2 + 0 = 4$

$f[3] = \min(f[1]+(5-0)^2, f[2]+(5-2)^2) = \min(25, 4+9=13) = 13$.

数据范围与提示

对于 100% 的数据，满足：

• $2 \le n \le 5 \times 10^5$
• $0 \le C \le 10^9$
• $0 \le x_1 < x_2 < \dots < x_n \le 10^9$
• 答案保证在 64 位有符号整数范围内。

提示： 本题的 DP 转移方程为：

$$f[i] = \min_{1 \le j < i} \left( f[j] + (x_i - x_j)^2 + C(x_i - x_j) \right)$$

展开平方项：

$$f[i] = \min_{j < i} \left( f[j] + x_i^2 - 2x_i x_j + x_j^2 + C x_i - C x_j \right)$$

整理得：

$$f[i] = x_i^2 + C x_i + \min_{j < i} \left( (f[j] + x_j^2 - C x_j) - 2x_i x_j \right)$$

令 $A_j = f[j] + x_j^2 - C x_j$，$B_j = -2 x_j$。 则我们需要求 $\min_{j < i} (A_j + B_j x_i)$。 这是一个典型的“半平面交”或“动态凸包”问题。由于 $x_i$ 单调递增，且 $B_j$（即斜率）随 $j$ 增大而减小（因为 $x_j$ 增大，$-2x_j$ 减小），我们可以使用单调队列维护下凸壳，从而将复杂度优化至 $O(n)$。

注意：由于 $C$ 和 $x_i$ 可能很大，中间计算过程必须使用 long long。