题目描述

给你一个长度为 $n$ 的数列 $a_1, a_2, \ldots, a_n$。

你可以对这个数列进行任意次操作，每次操作你可以选择将数列中某个元素的数值加 $1$ 或减 $1$。

操作结束后你有一次机会将这个数列从小到大排序，你希望排序后的数列是一个等差数列。

求：使排序后的数列 $a$ 是等差数列所需的最少操作次数？

输入格式

第一行，一个整数 $n$，表示数列长度。

第二行，$n$ 个整数 $a_1, a_2, \ldots, a_n$，两两之间以一个空格分隔。

输出格式

输出一个整数，表示是排序后的数列 $a$ 是等差数列所需的最少操作次数。

样例

5
5 1 14 9 12

3

8
1 3 5 7 9 11 13 17

2

说明/提示

样例解释

样例1：

一种最优解是操作 $3$ 次：令 $a_2$ 加 $1$，$a_4$ 减 $1$，$a_5$ 减 $1$，数列变为 $a = [5, 2, 14, 8, 11]$，排序后变为 $a = [2, 5, 8, 11, 14]$，是一个公差为 $3$ 的等差数列。

样例2：

一种最优解是操作 $2$ 次：每次操作均令 $a_8$ 减 $1$，最终数列变为 $a = [1, 3, 5, 7, 9, 11, 13, 15]$，是一个公差为 $2$ 的等差数列。

数据规模与约定

• 对于 $30\%$ 的数据，$n \le 20, a_i \le 1000$
• 对于 $60\%$ 的数据，$n \le 2000, a_i \le 10^9$
• 对于 $100\%$ 的数据，$1 \le n \le 2 \cdot 10^5, 1 \le a_i \le 10^{12}$