← 返回题目列表

Codeforces · 978/D

D. 几乎算术级数

中文机器翻译题面 查看原题

坡旅甲喜欢算术级数。如果对于每个 $$$i$$$ ($$$1 \le i < n$$$) 值 $$$a_{i+1} - a_i$$$ 相同,则序列 $$$[a_1, a_2, \dots, a_n]$$$ 称为算术级数。例如,序列 $$$[42]$$$、$$$[5, 5, 5]$$$、$$$[2, 11, 20, 29]$$$ 和 $$$[3, 2, 1, 0]$$$ 是算术级数,但 $$$[1, 0, 1]$$$、$$$[1, 3, 9]$$$ 和 $$$[2, 3, 1]$$$ 不是。

根据定义,任何长度为 1 或 2 的序列都是算术级数。

Polycarp 找到了一些正整数序列 $$$[b_1, b_2, \dots, b_n]$$$。他同意将每个元素最多更改一个。换句话说,对于每个元素,正好有三个选项:一个元素可以减少$$$1$$$,一个元素可以增加$$$1$$$,一个元素可以保持不变。

确定 $$$b$$$ 中可以更改的最小可能元素数(恰好为 1),以便序列 $$$b$$$ 成为算术级数,或者报告这是不可能的。

结果序列可能包含等于 $$$0$$$ 的元素。

输入

第一行包含一个整数 $$$n$$$ $$$(1 \le n \le 100\,000)$$$ — $$$b$$$ 中的元素数量。

第二行包含序列 $$$b_1, b_2, \dots, b_n$$$ $$$(1 \le b_i \le 10^{9})$$$。

输出

如果无法通过所描述的运算得出算术级数,则打印 -1。在另一种情况下,打印非负整数 - 使给定序列成为算术级数所需更改的最小元素数。唯一允许的操作是对元素加/减 1(不能对同一位置使用两次操作)。

示例

输入 #1

4
24 21 14 10

输出 #1

3

输入 #2

2
500 500

输出 #2

0

输入 #3

3
14 5 1

输出 #3

-1

输入#4

5
1 3 6 9 12

输出#4

1

注意

在第一个示例中,Polycarp 应增加 $$$1$$$ 上的第一个数字,减少 $$$1$$$ 上的第二个数字,增加 $$$1$$$ 上的第三个数字,第四个数字应保持不变。因此,波利卡普将三个元素改为一个后,他的序列就等于 $$$[25, 20, 15, 10]$$$,这是一个算术级数。

在第二个例子中,Polycarp 不应该改变任何东西,因为他的序列是一个算术级数。

在第三个示例中,不可能进行算术级数。

在第四个示例中,Polycarp 应该只更改第一个元素,他应该减少其中一个元素。之后他的序列将看起来像 $$$[0, 3, 6, 9, 12]$$$,这是一个算术级数。