题目描述

给定\(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)