蓝桥杯2022年第十三届决赛真题-好等差数列

等差数列是指从第二项开始，每一项与它前一项的差为同一个常数的数列，这个常数称为等差数列的公差。公差为整数的等差数列称为“好等差数列”。

一个数列到“好等差数列”的距离定义如下：找到一个最小的非负整数 k，使得将这个数列中的 k 个数修改后（可以修改为任意值），数列可以变为一个“好等差数列”，就称这个数列到“好等差数列”的距离为 k。例如，数列 (1, 2, 3, 5) 到“好等差数列”的距离为 1，因为将最后一个数字修改为 4 之后， (1, 2, 3, 4) 就是一个公差为 1 的“好等差数列”。

小蓝现在有一个长度为 n 的数列 A = (a₀, a₁, · · · , a_n−1) 。小蓝会对这个数列进行 m 次修改操作，每次修改数列中的一个元素，每次修改过后，小蓝都想知道当前的数列到“好等差数列”的距离是多少，请你帮他计算。

输入的第一行包含一个整数 n，表示数列的长度。

第二行包含 n 个整数 a₀, a₁, · · · , a_n−1，相邻两个整数之间用一个空格分隔。

第三行包含一个整数 m ，表示修改的次数。

接下来 m 行，每行包含两个整数 p, v，用一个空格分隔，表示将数列 A 中下标为 p 的元素修改为 v。

3
0 1 7
2
1 0
2 0

1 0

第一次修改后，数列 A = (0, 0, 7)，它到“好等差数列”的距离为 1，即至少修改其中一个元素后数列 A 就可以变成“好等差数列”。有多种实现方案：1）将第三个元素更改为 0 变为 (0, 0, 0) 是一个“好等差数列”，公差为 0；2）将第一个元素更改为 −7 变为 (−7, 0, 7) 也是一个“好等差数列”，公差为 7。注意上述两种方案中提到的更改并不是真的对数列 A 进行修改，而是为了表述数列是如何转化到“好等差数列”的。

第二次修改后，数列 A = (0, 0, 0)，他已经是一个“好等差数列”了，所以答案就是 0 。

对于 20% 的评测用例，1 ≤ n, m ≤ 10 ，0 ≤ a_i , v ≤ 10；

对于 50% 的评测用例，1 ≤ n ≤ 100 ，1 ≤ m ≤ 1000 ，0 ≤ a_i , v ≤ 10000 ；

对于所有评测用例，1 ≤ n, m ≤ 1000 ，0 ≤ a_i , v ≤ 10000 ，0 ≤ p ≤ n − 1。注意，以上为输入数据的限制，在判断是否为“好等差数列”时，修改的数可以超过 0 至 10000 的范围。