#include <stdio.h>
#include <string.h>
const int N = 500005;
typedef long long LL;
int n, m;
LL f[N], s[N];
int que[N], C[N];
inline LL min(LL a, LL b) {return a < b ? a : b;}
inline LL max(LL a, LL b) {return a > b ? a : b;}
inline LL G(int j, int k) {return s[j]*s[j]-s[k]*s[k] + f[j] - f[k];}
inline LL g(int j, int k) {return 2*(s[j]-s[k]);}
int main() {
while( scanf("%d %d", &n, &m) != EOF ) {
s[0] = 0;
for(int i = 1; i <= n; i ++) {
scanf("%d", C + i);
s[i] = s[i-1] + C[i];
}
f[0] = 0;
int head = 0, tail = 0;
que[0]= 0;
que[++tail] = 1; f[1] = s[1]*s[1] + m;
for(int i = 2; i < n + 1; i ++) {
while( head < tail && s[i] * g(que[head+1], que[head]) >= G(que[head+1], que[head]) )
head ++;
f[i] = f[que[head]] + (s[i]-s[que[head]])*(s[i]-s[que[head]]) + m;
while( head < tail && G(que[tail], que[tail-1])*g(i, que[tail]) >=
G(i, que[tail])*g(que[tail], que[tail-1]) ) tail --;
que[++tail]= i;
}
printf("%I64d\n", f[n]);
}
}
/*
dp[i]= min{ dp[j]+ ( sum[i]- sum[j] )* ( sum[i]- sum[j] )+ m } ( i< j );
假設(shè) j> k, 對于 i, 要使決策 j 優(yōu)于決策 k
則有 dp[j]+ ( sum[i]- sum[j] )* ( sum[i]- sum[j] )+ m<
dp[k]+ ( sum[i]- sum[k] )* ( sum[i]- sum[k] )+ m
得到 dp[j]+ sum[j]* sum[j]- dp[k]- sum[k]* sum[k]<
2* sum[i]* ( sum[j]- sum[k] )
令 F[j,k]= (dp[j]+sum[j]*sum[j]-dp[k]-dp[k]*sum[k])/(2*(sum[j]-sum[k]))
對于當(dāng)前 i, j 比 k 優(yōu)等價于 F[j,k]< sum[i],所以計算當(dāng)前 i 的值時
可以剔除 F[j,k]< sum[i] 的 k 值。
進(jìn)一步，對于 k< j< i< t
如果 F[j,k]> F[i, j]. F[i,j]與 sum[t] 有兩種關(guān)系
1. F[i,j]<= sum[t] 可知 i 比 j 優(yōu)
2. F[i,j]> sum[t] 得到 F[j,k]> sum[t] 同樣知 k 比 j 優(yōu)
綜上知 j 不會是最優(yōu)的
進(jìn)隊時, 對滿足 F[j,k]> F[i,j] 條件的 i，則可以
剔除 j.
*/