题目描述

$N$ 個の足場があります。 足場には $1,\ 2,\ \ldots,\ N$ と番号が振られています。 各 $i$ ($1\ \leq\ i\ \leq\ N$) について、足場 $i$ の高さは $h_i$ です。 ここで、$h_1\ <\ h_2\ <\ \cdots\ <\ h_N$ です。

最初、足場 $1$ にカエルがいます。 カエルは次の行動を何回か繰り返し、足場 $N$ まで辿り着こうとしています。

• 足場 $i$ にいるとき、足場 $i\ +\ 1,\ i\ +\ 2,\ \ldots,\ N$ のどれかへジャンプする。 このとき、ジャンプ先の足場を $j$ とすると、コスト $(h_j\ -\ h_i)^2\ +\ C$ を支払う。

カエルが足場 $N$ に辿り着くまでに支払うコストの総和の最小値を求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $C$ $h_1$ $h_2$ $\ldots$ $h_N$

输出格式

カエルが支払うコストの総和の最小値を出力せよ。

题目大意

有 $N$ 个石头，编号为 $1,2,\dots,N$，第 $i$ 个高为 $h_i$。保证 $h$ 严格单调递增。

有一只青蛙在第一个石头上，它可以跳到石头编号为 $i+1,i+2,\dots,N$。当他跳到编号 $j$ 石头时的花费是 $(h_i-h_j)^2+C$。求跳到编号为 $N$ 石头的最小花费。

5 6
1 2 3 4 5

20

2 1000000000000
500000 1000000

1250000000000

8 5
1 3 4 5 10 11 12 13

62

提示

制約

• 入力はすべて整数である。
• $2\ \leq\ N\ \leq\ 2\ \times\ 10^5$
• $1\ \leq\ C\ \leq\ 10^{12}$
• $ 1\ \leq\ h_1\ <\ h_2\ <\ \cdots\ <\ h_N\ \leq\ 10^6 $

Sample Explanation 1

足場 $1$ → $3$ → $5$ と移動すると、コストの総和は $ ((3\ -\ 1)^2\ +\ 6)\ +\ ((5\ -\ 3)^2\ +\ 6)\ =\ 20 $ となります。

Sample Explanation 2

答えは 32-bit 整数型に収まらない場合があります。

Sample Explanation 3

足場 $1$ → $2$ → $4$ → $5$ → $8$ と移動すると、コストの総和は $ ((3\ -\ 1)^2\ +\ 5)\ +\ ((5\ -\ 3)^2\ +\ 5)\ +\ ((10\ -\ 5)^2\ +\ 5)\ +\ ((13\ -\ 10)^2\ +\ 5)\ =\ 62 $ となります。