题目描述

借助于能量球所蕴含的巨大能量，以及 sideman 所掌握的 Gliese 星球强大的工业技术，sideman 成功制造出一艘名为“方 舟”的宇宙飞船。而宇宙飞船的控制系统则被称为“方舟系统”。

方舟系统的存储器是一种顺序读取的磁带，上面记录有 N 个非负整数。而系统会按照这样的方式读取磁带：系统先读取 一个整数 S1，之后系统会连续读取 S1 个数据，然后系统会读 取一个整数 S2，之后系统会连续读取 S2 个数据……依此类推。 但是，如果系统读取完磁带的最后一个数之后，还试图读取下 一个数，那么系统就会崩溃。

sideman 现在发现，由于他的失误，他所准备的磁带有可能会使系统崩溃掉……为了避 免这种情况的发生他需要修改磁带。由于磁带的特殊构造，把一个数 A 改成另一个非负整 数 B 的代价为|A - B|。现在 sideman 想知道把磁带修改为合法的所需要的最小代价是多少。

输入格式

包含两行。

第一行是一个正整数 N，表示磁带的数字数目。

第二行包含 N 个非负整数，表示磁带的数据。

输出格式

输出一个非负整数表示最小代价。

样例数据

input

4

2 2 2 2

output

1

数据规模与约定

对于 30% 的数据，保证 $N≤1000$。

对于 70% 的数据，保证 $N≤10^5$。

对于 100% 的数据，保证 $N≤10^6$，答案不大于 $10^9$。

时间限制：$1 \text {s}$

空间限制：$256 \text {MB}$