等差數(shù)列是指從第二項(xiàng)開始，每一項(xiàng)與它前一項(xiàng)的差為同一個(gè)常數(shù)的數(shù)列，這個(gè)常數(shù)稱為等差數(shù)列的公差。公差為整數(shù)的等差數(shù)列稱為“好等差數(shù)列”。

一個(gè)數(shù)列到“好等差數(shù)列”的距離定義如下：找到一個(gè)最小的非負(fù)整數(shù) k，使得將這個(gè)數(shù)列中的 k 個(gè)數(shù)修改后（可以修改為任意值），數(shù)列可以變?yōu)橐粋€(gè)“好等差數(shù)列”，就稱這個(gè)數(shù)列到“好等差數(shù)列”的距離為 k。例如，數(shù)列 (1, 2, 3, 5) 到“好等差數(shù)列”的距離為 1，因?yàn)閷⒆詈笠粋€(gè)數(shù)字修改為 4 之后， (1, 2, 3, 4) 就是一個(gè)公差為 1 的“好等差數(shù)列”。

小藍(lán)現(xiàn)在有一個(gè)長(zhǎng)度為 n 的數(shù)列 A = (a₀, a₁, · · · , a_n?1) 。小藍(lán)會(huì)對(duì)這個(gè)數(shù)列進(jìn)行 m 次修改操作，每次修改數(shù)列中的一個(gè)元素，每次修改過(guò)后，小藍(lán)都想知道當(dāng)前的數(shù)列到“好等差數(shù)列”的距離是多少，請(qǐng)你幫他計(jì)算。

輸入的第一行包含一個(gè)整數(shù) n，表示數(shù)列的長(zhǎng)度。

第二行包含 n 個(gè)整數(shù) a₀, a₁, · · · , a_n?1，相鄰兩個(gè)整數(shù)之間用一個(gè)空格分隔。

第三行包含一個(gè)整數(shù) m ，表示修改的次數(shù)。

接下來(lái) m 行，每行包含兩個(gè)整數(shù) p, v，用一個(gè)空格分隔，表示將數(shù)列 A 中下標(biāo)為 p 的元素修改為 v。

3
0 1 7
2
1 0
2 0

1 0

第一次修改后，數(shù)列 A = (0, 0, 7)，它到“好等差數(shù)列”的距離為 1，即至少修改其中一個(gè)元素后數(shù)列 A 就可以變成“好等差數(shù)列”。有多種實(shí)現(xiàn)方案：1）將第三個(gè)元素更改為 0 變?yōu)?(0, 0, 0) 是一個(gè)“好等差數(shù)列”，公差為 0；2）將第一個(gè)元素更改為 ?7 變?yōu)?(?7, 0, 7) 也是一個(gè)“好等差數(shù)列”，公差為 7。注意上述兩種方案中提到的更改并不是真的對(duì)數(shù)列 A 進(jìn)行修改，而是為了表述數(shù)列是如何轉(zhuǎn)化到“好等差數(shù)列”的。

第二次修改后，數(shù)列 A = (0, 0, 0)，他已經(jīng)是一個(gè)“好等差數(shù)列”了，所以答案就是 0 。

對(duì)于 20% 的評(píng)測(cè)用例，1 ≤ n, m ≤ 10 ，0 ≤ a_i , v ≤ 10；

對(duì)于 50% 的評(píng)測(cè)用例，1 ≤ n ≤ 100 ，1 ≤ m ≤ 1000 ，0 ≤ a_i , v ≤ 10000 ；

對(duì)于所有評(píng)測(cè)用例，1 ≤ n, m ≤ 1000 ，0 ≤ a_i , v ≤ 10000 ，0 ≤ p ≤ n ? 1。注意，以上為輸入數(shù)據(jù)的限制，在判斷是否為“好等差數(shù)列”時(shí)，修改的數(shù)可以超過(guò) 0 至 10000 的范圍。