Массив \(a_1, a_2, \ldots, a_n\) называется хорошим, если и только если для любого подотрезка \(1 \leq l \leq r \leq n\), выполняется следующее: \(a_l + a_{l + 1} + \ldots + a_r = \frac{1}{2}(a_l + a_r) \cdot (r - l + 1)\).
Вам дан массив целых чисел \(a_1, a_2, \ldots, a_n\). За одну операцию вы можете заменить один любой элемент массива на любое вещественное число. Определите минимальное число операций, необходимое, чтобы сделать массив хорошим.
Выходные данные
Для каждого набора входных данных выведите одно целое число: минимальное число элементов, которое нужно заменить, чтобы массив стал хорошим.
Примечание
В первом примере массив хороший изначально.
Во втором примере один из возможных хороших массивов — \([1, 1, \underline{1}, \underline{1}]\) (замененные элементы подчеркнуты).
В третьем примере массив хороший изначальное.
Во четвертом примере один из возможных хороших массивов — \([\underline{-2.5}, -2, \underline{-1.5}, -1, \underline{-0.5}, 0]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
4
1 2 3 4
4
1 1 2 2
2
0 -1
6
3 -2 4 -1 -4 0
1
-100
|
0
2
0
3
0
|