题目描述

M省要举办一场比赛，比赛地点是由 $n$ 个城市组成的环形城市群。这些城市按顺时针编号为 $1,2,...,n$。每个城市都连接与它相邻的城市（与相邻的城市距离均为为 $1$），即城市 $i$ 与城市 $i - 1$ 和城市 $i + 1$ 可以相互到达（如果存在的话）。由于是环形，城市 $1$ 与城市 $n$ 也可以相互到达。

城市 $i$ 的参赛人数为 $a_i$ 人，但是为了便于管理，只有至多 $k$ 个城市对外开放，参赛者只能从开放城市进入，然后通过相邻城市到达其参赛的城市。由于参赛者们长途跋涉已经很累了，每位参赛者移动 $d$ 距离会消耗 $d^2$ 的体力。

参赛者们都很聪明，他们会自己选择距离目标城市最近的开放城市进入。

已知编号最小的开放城市为城市 $x$，江桥想知道，通过合理地选择剩下的开放的城市，使得所有参赛者到达目标城市的总体力消耗最小是多少。

输入格式

第一行输入三个正整数 $n,k,x$。

第二行输入 $n$ 个正整数，表示 $a_i$ 。

输出格式

输出一个整数，代表答案。

6 2 2
2 5 4 2 6 2

10

6 2 1
4 2 5 6 3 2

12

样例解释

对于样例 $1$，开放城市 $2$ 和城市 $5$，城市 $1,2,3$ 的参赛者从城市 $2$ 进入，消耗的体力总和为 $2 + 0 + 4 = 6$，城市 $4,5,6$ 的参赛者从城市 $5$ 进入，消耗的体力总和为 $2 + 0 + 2 = 4$，因此总体力消耗为 $10$，容易证明这就是最优解。

数据规模与约定

下发文件

下发文件对应子任务 $3,4,5$。

有合理的子任务依赖。

对于 $100\%$ 的数据：保证 $1 \leq n \leq 2 \times 10^3, 1 \leq k \leq min(n,10),1 \leq a_i \leq 10^6$。