好等差数列 ### 问题描述 等差数列是指从第二项开始, 每一项与它前一项的差为同一个常数的数列, 这个常数称为等差数列的公差。公差为整数的等差数列称为 “好等差数列”。 一个数列到 “好等差数列” 的距离定义如下：找到一个最小的非负整数 $k$, 使得将这个数列中的 $k$ 个数修改后 (可以修改为任意值), 数列可以变为一 个 “好等差数列”, 就称这个数列到 “好等差数列” 的距离为 $k$ 。例如, 数列 $(1,2,3,5)$ 到 “好等差数列” 的距离为 1 , 因为将最后一个数字修改为 4 之后, $(1,2,3,4)$ 就是一个公差为 1 的 “好等差数列”。 小蓝现在有一个长度为 $n$ 的数列 $A=\left(a_{0}, a_{1}, \cdots, a_{n-1}\right)$ 。小蓝会对这个数列 进行 $m$ 次修改操作, 每次修改数列中的一个元素, 每次修改过后, 小蓝都想知 道当前的数列到 “好等差数列” 的距离是多少, 请你帮他计算。 ### 输入格式 输入的第一行包含一个整数 $n$, 表示数列的长度。 第二行包含 $n$ 个整数 $a_{0}, a_{1}, \cdots, a_{n-1}$, 相邻两个整数之间用一个空格分隔。 第三行包含一个整数 $m$, 表示修改的次数。 接下来 $m$ 行, 每行包含两个整数 $p, v$, 用一个空格分隔, 表示将数列 $A$ 中 下标为 $p$ 的元素修改为 $v_{\text {。 }}$ ### 输出格式 输出一行包含 $m$ 个整数, 相邻两个整数之间用一个空格分隔, 其中第 $i$ 个 整数表示经过前 $i$ 次修改操作之后, 数列到 “好等差数列” 的距离。 ### 样例输入 ```text 3 0 1 7 2 1 0 2 0 ``` ### 样例输出 ```text 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 \leq n, m \leq 10,0 \leq a_{i}, v \leq 10$ : 对于 $50 \\%$ 的评测用例, $1 \leq n \leq 100 ， 1 \leq m \leq 1000,0 \leq a_{i}, v \leq 10000$ ： 对于所有评测用例, $1 \leq n, m \leq 1000,0 \leq a_{i}, v \leq 10000,0 \leq p \leq n-1$ 。注 意, 以上为输入数据的限制, 在判断是否为 “好等差数列” 时, 修改的数可以 超过 0 至 10000 的范围。