You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

小明需要调试一段有$n$行代码，其中有$m$行有bug（位置锁定为$a_1, a_2, ..., a_m$，且$1 \le a_1 \lt a_2 < ... \lt a_m \le n$）。每次调试可选择运行前$i$行代码（从第$1$行顺序运行到第$i$行），耗时$i$秒，随后一次性修复这$i$行中的所有现存$bug$，修复时间为这$i$行中现存$bug$数量的四次方（$x^4$秒，$x$为现存$bug$数）。修复后，这$i$行中的$bug$将被彻底清除。求完成所有$bug$修复的最短总耗时。

输入格式

• 第一行：两个整数$n$和$m$（$1 \le m \le n \le 2×10^5$）。
• 第二行：$m$个整数$a_1, a_2, ..., a_m$（表示有$bug$的行号，按升序排列）。

输出格式

一行，一个整数，表示最短总耗时。

样例

输入

3 2  
1 3  

输出

6

样例2

输入

20 20  
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20  

输出

221

样例解释

对于第一个样例，先运行前1行（耗时1秒），修复1个bug（耗时1⁴=1秒）；再运行前3行（耗时3秒），修复1个bug（耗时1⁴=1秒），总耗时1+1+3+1=6秒。

对于第二个样例，通过分阶段运行前1, 2, ..., 13, 14, 16, 18, 20行达到最优解。

数据分布

$30\%$ 的样例，$1 \le m \le n \le 10$。 $1 \le a_1, a_2, ..., a_m \le n$

$60\%$ 的样例，$1 \le m \le n \le 1000$。 $1 \le a_1, a_2, ..., a_m \le n$

$100\%$ 的样例，$1 \le m \le n \le 2×10^5$。 $1 \le a_1, a_2, ..., a_m \le n$