An array $a_1, a_2, \ldots, a_n$ is good if and only if for every subsegment $1 \leq l \leq r \leq n$, the following holds: $a_l + a_{l + 1} + \ldots + a_r = \frac{1}{2}(a_l + a_r) \cdot (r - l + 1)$.

You are given an array of integers $a_1, a_2, \ldots, a_n$. In one operation, you can replace any one element of this array with any real number. Find the minimum number of operations you need to make this array good.


-----Input-----

The first line of input contains one integer $t$ ($1 \leq t \leq 100$): the number of test cases.

Each of the next $t$ lines contains the description of a test case.

In the first line you are given one integer $n$ ($1 \leq n \leq 70$): the number of integers in the array.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($-100 \leq a_i \leq 100$): the initial array.


-----Output-----

For each test case, print one integer: the minimum number of elements that you need to replace to make the given array good.


-----Examples-----

Input
5
4
1 2 3 4
4
1 1 2 2
2
0 -1
6
3 -2 4 -1 -4 0
1
-100
Output
0
2
0
3
0


-----Note-----

In the first test case, the array is good already.

In the second test case, one of the possible good arrays is $[1, 1, \underline{1}, \underline{1}]$ (replaced elements are underlined).

In the third test case, the array is good already.

In the fourth test case, one of the possible good arrays is $[\underline{-2.5}, -2, \underline{-1.5}, -1, \underline{-0.5}, 0]$.

Source: codeforces | Difficulty: MEDIUM
Tags: Mathematics

Geometry

Implementation

Complete search


Solutions:
from collections import Counter
for _ in range(int(input())):
	n = int(input())
	arr = list(map(float, input().split()))
	if n == 1:
		print(0)
	else:
		ans = float('inf')
		for i in range(n):
			ht = {}
			for j in range(i + 1, n):
				d = (arr[i] - arr[j]) / (i - j)
				if d in ht:
					ht[d] += 1
				else:
					ht[d] = 1
			if ht:
				ans = min(ans, n - 1 - max(ht.values()))
		print(ans)


from collections import defaultdict
mydict = defaultdict(lambda : 0)
cases = int(input())
for _ in range(cases):
	n = int(input())
	line = input().split()
	L = []
	for elem in line:
		L.append(int(elem))
	if n <= 2:
		print(0)
		continue
	consider = []
	for l in range(n - 1):
		mydict = defaultdict(lambda : 0)
		for r in range(l + 1, n):
			d = (L[r] - L[l]) / (r - l)
			mydict[d] += 1
		z = max(mydict.values())
		consider.append(z)
	z = max(consider)
	print(n - z - 1)


x = int(input())
for i in range(x):
	y = int(input())
	A = input().split()
	B = [0] * y
	maxi = 0
	if y == 1:
		print('0')
	else:
		for j in range(y):
			B[j] = int(A[j])
		for j in range(y - 1):
			C = []
			D = []
			for k in range(j + 1, y):
				a = (B[k] - B[j]) / (k - j)
				C.append(float(a))
			C.sort()
			max_count = 1
			curr_count = 1
			for i in range(1, len(C)):
				if C[i] == C[i - 1]:
					curr_count += 1
				else:
					curr_count = 1
				if curr_count > max_count:
					max_count = curr_count
			if max_count + 1 > maxi:
				maxi = max_count + 1
		print(len(A) - maxi)


import sys
import math
import bisect
from sys import stdin, stdout
from math import gcd, floor, sqrt, log
from collections import defaultdict as dd
from bisect import bisect_left as bl, bisect_right as br
sys.setrecursionlimit(100000000)

def solve():
	n = int(input())
	arr = list(map(int, input().split()))
	temp = 0
	ans = 0
	for i in range(n - 1):
		temp = 0
		d = dict()
		for j in range(i + 1, n):
			k = (arr[j] - arr[i]) * 1.0 / (i - j)
			d[k] = d.get(k, 0) + 1
			temp = max(temp, d[k])
		ans = max(ans, temp)
	return n - ans - 1

def main():
	t = int(input())
	while t:
		print(solve())
		t -= 1
main()


q = int(input())
for _ in range(q):
	n = int(input())
	a = [int(a) for a in input().split()]
	len_prog = 0
	for i in range(n):
		dct = {}
		for j in range(i + 1, n):
			name = (a[i] - a[j]) / (i - j)
			if name not in dct:
				dct[name] = {i, j}
			else:
				dct[name].add(j)
		for (k, v) in dct.items():
			if len_prog < len(v):
				len_prog = len(v)
	if n > 1:
		print(n - len_prog)
	else:
		print(0)


for iii in range(int(input())):
	n = int(input())
	q = list(map(int, input().split()))
	q1 = {}
	maxx = 0
	for i in range(n):
		q1 = {}
		for j in range(i + 1, n):
			x = (q[j] - q[i]) / (j - i)
			if x in q1:
				q1[x] += 1
			else:
				q1[x] = 1
		for i in q1:
			maxx = max(maxx, q1[i])
	print(n - 1 - maxx)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	best = 0
	for j in range(n - 1):
		s = {}
		for k in range(j + 1, n):
			if (l[k] - l[j]) * 10 ** 6 // (k - j) in s.keys():
				s[(l[k] - l[j]) * 10 ** 6 // (k - j)] += 1
			else:
				s[(l[k] - l[j]) * 10 ** 6 // (k - j)] = 1
		best = max(best, max(s.values()))
	print(n - 1 - best)


import sys
from math import sqrt, gcd
from collections import deque
sys.setrecursionlimit(10 ** 8)
I = lambda : int(input())
S = lambda : input().strip()
M = lambda : map(int, input().strip().split())
L = lambda : list(map(float, input().strip().split()))
mod = 1000000007
for _ in range(I()):
	n = I()
	arr = L()
	t = 0
	ans = 0
	for i in range(n - 1):
		t = 0
		di = {}
		for j in range(i + 1, n):
			d = (arr[j] - arr[i]) / (i - j)
			if d in di:
				di[d] += 1
			else:
				di[d] = 1
			t = max(t, di[d])
		ans = max(ans, t)
	print(n - 1 - ans)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	t = 0
	ans = 0
	for i in range(0, n - 1):
		t = 0
		d = {}
		for j in range(i + 1, n):
			k = (a[j] - a[i]) * 1.0 / (i - j)
			if k not in d:
				d[k] = 1
			else:
				d[k] += 1
			ans = max(ans, d[k])
	print(n - ans - 1)


class codeforce:

	def solve(self, n, a):
		t = 0
		result = 0
		for i in range(n - 1):
			t = 0
			di = {}
			for j in range(i + 1, n):
				if (a[j] - a[i]) * 1.0 / (i - j) in di:
					di[(a[j] - a[i]) * 1.0 / (i - j)] += 1
				else:
					di[(a[j] - a[i]) * 1.0 / (i - j)] = 1
				t = max(t, di[(a[j] - a[i]) * 1.0 / (i - j)])
			result = max(result, t)
		return n - result - 1
t = int(input())
while t > 0:
	n = int(input())
	arr = list(map(int, input().split()))
	res = codeforce()
	print(res.solve(n, arr))
	t -= 1


from collections import Counter
import sys
fin = sys.stdin

def solve(a, n):
	if n == 1:
		return 0
	count = []
	for i in range(n - 1):
		for j in range(i + 1, n):
			delta = a[j] - a[i]
			steps = j - i
			d = delta / steps
			a0 = a[i] - d * i
			count.append((int(a0 * 1000000000), int(d * 1000000000)))
	count = Counter(count)
	(_, count) = count.most_common(1)[0]
	for i in range(1, n):
		if count <= i * (i + 1) // 2:
			return n - i - 1
t = int(fin.readline())
for test in range(t):
	n = int(fin.readline())
	a = list(map(int, fin.readline().split()))
	print(solve(a, n))


from collections import defaultdict
from collections import defaultdict, Counter
n = int(input())
results = []
for i in range(n):
	m = int(input())
	a = [int(x) for x in input().strip().split(' ')]
	if m == 1:
		results.append(0)
	else:
		tmp_res = m
		for j in range(m):
			line = []
			for k in range(m):
				if j != k:
					m1 = (a[k] - a[j]) / (k - j)
				else:
					m1 = 0
				line.append(m1)
			counter = Counter(line)
			maxi = max(counter, key=counter.get)
			if abs(maxi) == 0.0:
				tmp_res = min(tmp_res, m - counter[maxi])
			else:
				tmp_res = min(tmp_res, m - counter[maxi] - 1)
		results.append(tmp_res)
for line in results:
	print(line)


from collections import Counter
for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if n == 2 or n == 1:
		print(0)
		continue
	mx = 0
	for j in range(n):
		l = []
		for k in range(n):
			if j < k:
				l.append((a[k] - a[j]) / (k - j))
			elif j > k:
				l.append((a[j] - a[k]) / (j - k))
		c = Counter(l)
		if max(c.values()) > mx:
			mx = max(c.values())
	print(n - mx - 1)


from collections import defaultdict

def answer(n, arr):
	if n == 1 or n == 2:
		return 0
	maximum = 0
	for i in range(len(arr)):
		d = defaultdict(int)
		for j in range(len(arr)):
			if j != i:
				d[(arr[i] - arr[j]) / (i - j)] += 1
		if max(d.values()) > maximum:
			maximum = max(d.values())
	return n - maximum - 1
t = int(input())
for k in range(t):
	n = int(input())
	inp = input().split()
	arr = []
	for i in inp:
		arr.append(int(i))
	print(answer(n, arr))


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	dif = []
	for i in range(1, n):
		dif.append(arr[i] - arr[i - 1])
	s = set(dif)
	if n <= 2 or len(s) == 1:
		print(0)
		continue
	res = 0
	for i in range(n - 1):
		ans = {}
		ans1 = 0
		for j in range(i + 1, n):
			slope = (arr[j] - arr[i]) / (j - i)
			if slope not in ans:
				ans[slope] = 1
			else:
				ans[slope] += 1
			ans1 = max(ans.values())
		res = max(res, ans1)
	print(n - res - 1)


import os, sys
from collections import Counter
MAXN = 100000000
MAXN = 1000000000

def read_int():
	return int(sys.stdin.readline())

def read_arr():
	return list(map(int, sys.stdin.readline().strip().split()))

def solve(a, N):
	if N <= 2:
		return 0
	counter = Counter()
	for i in range(N - 1):
		for j in range(i + 1, N):
			d = (a[j] - a[i]) / (j - i)
			a0 = a[i] - i * d
			counter[int(a0 * MAXN), int(d * MAXN)] += 1
	(_, largest_count) = counter.most_common(1)[0]
	ans = -1
	for n in range(2, N + 1):
		if n * (n - 1) // 2 >= largest_count:
			ans = N - n
			break
	return ans
T = read_int()
while T > 0:
	N = read_int()
	a = read_arr()
	print(solve(a, N))
	T -= 1


import math as mt
for _ in range(int(input())):
	n = int(input())
	l = [int(i) for i in input().split()]
	if n == 1:
		print(0)
		continue
	mn = 10 ** 7
	ans = []
	for i in range(n):
		d = []
		for j in range(n):
			if i == j:
				continue
			d1 = (l[j] - l[i]) / (j - i)
			d += [d1]
		d.sort()
		mx = -10 ** 9
		cnt = 1
		for j in range(1, len(d)):
			if d[j] == d[j - 1]:
				cnt += 1
			else:
				if cnt > mx:
					mx = cnt
				cnt = 1
		if cnt > mx:
			mx = cnt
		ans += [mx]
	print(n - max(ans) - 1)


import collections
epsilon = 10 ** (-6)
t = int(input())
for k in range(t):
	n = int(input())
	l = [int(x) for x in input().split()]
	res = 1
	if n <= 2:
		res = n - 1
	else:
		for i in range(n):
			diff = collections.defaultdict(int)
			for j in range(n):
				if i != j:
					diff[(l[j] - l[i]) / (j - i)] += 1
			res = max(res, max(diff.values()))
	print(n - res - 1)


from math import *
from collections import *
from itertools import *
from functools import *
from bisect import *
from heapq import *
from operator import *
from sys import *
setrecursionlimit(100000000)
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	ans = 1
	if n <= 2:
		print(0)
		continue
	for i in range(n):
		d = defaultdict(int)
		for j in range(n):
			if i != j:
				d[(l[j] - l[i]) / (j - i)] += 1
		if d:
			ans = max(ans, max(d.values()))
	print(n - 1 - ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if n == 1 or n == 2:
		print(0)
	else:
		best = 0
		for i in range(n):
			c = {}
			for j in range(n):
				if i != j:
					if (a[i] - a[j]) / (i - j) in c:
						c[(a[i] - a[j]) / (i - j)] += 1
					else:
						c[(a[i] - a[j]) / (i - j)] = 1
			best = max(best, max(c.values()))
		print(n - 1 - best)


T = int(input())
for t in range(T):
	n = int(input())
	s = [int(x) for x in input().split()]
	score = []
	for i in range(n):
		slopes = dict()
		for j in range(n):
			if j != i:
				slope = (s[i] - s[j]) / (i - j)
				if slope not in slopes:
					slopes[slope] = 1
				else:
					slopes[slope] += 1
		Max = 0
		for i in slopes:
			if slopes[i] > Max:
				Max = slopes[i]
		score.append(n - Max - 1)
	print(min(score))


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	count = 0
	if n == 1:
		print(0)
	elif n == 2:
		print(0)
	else:
		not_to_change = 0
		for i in range(n):
			d = Counter()
			for j in range(n):
				if i != j:
					temp_diff = (arr[i] - arr[j]) / (i - j)
					d[temp_diff] += 1
			temp_max = max(d.values())
			if temp_max > not_to_change:
				not_to_change = temp_max
		to_change = n - 1 - not_to_change
		print(to_change)


t = int(input())
for _ in range(t):
	n = int(input())
	li = list(map(int, input().split()))
	max_R = 0
	for i in range(n):
		diff_arr = {}
		for j in range(n):
			if i != j:
				temp = (li[i] - li[j]) / (i - j)
				if temp not in diff_arr:
					diff_arr[temp] = 0
				diff_arr[temp] += 1
		max_r = 0
		for k in diff_arr.values():
			if k > max_r:
				max_r = k
		if max_r > max_R:
			max_R = max_r
	print(n - max_R - 1)


def mp(p):
	n = len(p)
	if n < 3:
		return n
	max_val = 0
	for i in p:
		d = {}
		dups = 0
		cur_max = 0
		for j in p:
			if i != j:
				if j[0] == i[0]:
					s = 'inf'
				else:
					s = float(j[1] - i[1]) / float(j[0] - i[0])
				d[s] = d.get(s, 0) + 1
				cur_max = max(cur_max, d[s])
			else:
				dups += 1
		max_val = max(max_val, cur_max + dups)
	return max_val
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	points = []
	for i in range(n):
		points.append([i, a[i]])
	print(n - mp(points))


for i in range(int(input())):
	n = int(input())
	arr = (*map(int, input().split()),)
	if n == 1:
		print(0)
	else:
		ans = float('inf')
		for j in range(n):
			freq = {}
			for i in range(n):
				if i != j:
					d = round((arr[i] - arr[j]) / (i - j), 10)
					freq[d] = freq.get(d, 0) + 1
			ans = min(ans, n - 1 - max(freq.values()))
		print(ans)


def res():
	t = int(input())
	st = list(map(int, input().split()))
	if t <= 2:
		return 0
	best_res = t
	for i in range(t):
		for j in range(i + 1, t):
			res = t - 2
			d = (st[i] - st[j]) / (j - i)
			cur = st[j]
			cur_j = j
			for k in range(j + 1, t):
				if (cur - st[k]) / (k - cur_j) == d:
					res -= 1
					cur = st[k]
					cur_j = k
			if res < best_res:
				best_res = res
	return best_res
n = int(input())
for _ in range(n):
	i = res()
	print(i)