该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定$N$个非负整数$a_1, a_2 \cdots a_N$，定义$N$元函数$f(x_1, x_2 \cdots x_N)$：
函数的定义域为$N$维整数空间，即$x_i \in \mathbf{Z}, i=1,2 \cdots N$。
（1）若$x_1 \le x_2 \le \cdots \le x_N$，或者$x_1 \ge x_2 \ge \cdots \ge x_N$，则：
$f(x_1, x_2 \cdots x_N) = \displaystyle\sum_{i=1}^{N} \lvert a_i - x_i \rvert$
（2）否则：
$f(x_1, x_2 \cdots x_N) = +\infty$
求该函数的最小值。

输入格式及数据规模

第一行是一个正整数$N$；
第二行是$N$个非负整数$a_1, a_2 \cdots a_N$。
20%的数据：$N \le 5$
另外20%的数据：$N \le 1000, \phantom{x} a_i \le 1000$
另外20%的数据：$N \le 100$
100%的数据：$N \le 2000, \phantom{x} a_i \le 10^9$。

输出格式

一个整数，该函数的最小值。

样例

input

7
1 3 2 4 5 3 9

output

3

限制

Time limit: 1 sec
Memory limit: 128 megabytes

来源

From PKU Online Judge (POJ 3666)