题目描述

“不惧极端天气休闲攀登协会”的成员们，在七年前的今天完成了他们的第一次成功登顶。

当时，大家排成一行拍了一张合照。然而，照片看起来有些杂乱，因为登山者并没有按照身高顺序站立，而现在已经无法重新排列他们的位置。

因此，只能从照片中裁掉一部分人。

删除部分登山者后的照片

上图中原本有 $11$ 名登山者。为了得到样例输入 3 的一个最优方案，其中 $4$ 人被裁掉，剩下 $7$ 人。

一个最优方案应尽量减少编辑后照片中可见空缺的大小和数量。

若连续裁掉的一段共有 $w$ 个人，则这一段空缺产生的代价为 $w^2$。总成本定义为所有空缺代价之和。

例如，若裁掉了两个彼此分离的单人，并裁掉了一对相邻的人，则总成本为

请通过裁掉一部分登山者，使照片中剩余人员的身高从左到右构成一个非递减序列，并求能够达到的最小总成本。

输入格式

第一行包含一个整数 $n$，表示照片中的人数。

第二行包含 $n$ 个整数 $h_1,h_2,\ldots,h_n$，表示这些人从左到右的身高。

输出格式

输出一个整数，表示使剩余登山者的身高构成非递减序列时，裁剪空缺总成本的最小值。

数据范围

• $1\le n\le 10^6$；
• $0\le h_i\le 10^6$。

样例 1

输入

7
1 2 3 0 5 6 7

输出

1

样例 2

输入

9
4 5 6 4 2 3 6 6 6

输出

8

样例 3

输入

11
3 6 12 7 7 7 6 8 10 5 5

输出

6