In a Circular City, there are $n$ houses, numbered from 1 to n and arranged in 1,2,...,n,1,2,...
Chef needs to deliver packages to $m$ (m≤n) houses. 

Chef is initially at house 1. Chef decides an integer $x$ and stops after every $x$ houses. i.e- if $n=7$ and $x=2$. He will stop at 1,3,5,7,2,... He may deliver a package when he stops at a house. His work is done when all the packages are delivered.

What is the minimum number of times Chef has to stop, if he can choose any $x$ ?

__Note__: Starting point (1) is also counted in number of stops

------ Input: ------

First line will contain $n, m$, denoting number of houses and number of packages respectively.
Next line contains $m$ distinct space separated integers denoting the houses

------ Output: ------
Single line containing an integer denoting minimum number of stops.

------ Constraints  ------
$3 ≤ n ≤ 1000$
$1 ≤ m ≤ n$

----- Sample Input 1 ------ 
5 3
1 2 4
----- Sample Output 1 ------ 
3
----- explanation 1 ------ 
For first input,
If Chef chooses $x=3$, he will stop at 1, 4, 2 before delivering all the packages.

----- Sample Input 2 ------ 
6 2
3 4
----- Sample Output 2 ------ 
4
----- explanation 2 ------ 
For second,
If Chef chooses $x=1$, he will stop at 1, 2, 3, 4 before delivering all the packages.

Difficulty: MEDIUM_HARD
Tags: Complete search

Constructive algorithms

Data structures

Ad-hoc
Skill types: Data structures

Complete search

Starter code:

Solutions:
(n, m) = map(int, input().split())
l = set(list(map(int, input().split())))
ans = []
for x in range(n + 1):
	(z, ct, b) = (1, 0, 0)
	while True:
		if z == 1 and ct != 0:
			break
		if b == m:
			break
		if z in l:
			b += 1
		if z + x <= n:
			z += x
		else:
			k = z + x
			z = k - n
		ct += 1
	if b == m:
		ans.append(ct)
print(min(ans))


(m, n) = map(int, input().split())
v = [int(x) for x in input().split()]
ans = m
for i in range(1, m):
	cpy = v.copy()
	(k, cnt, l) = (1, 1, [1])
	while len(cpy) != 0:
		if k in cpy:
			cpy.remove(k)
		if len(cpy) == 0:
			break
		k += i
		cnt += 1
		if k > m:
			k = k - m
		if k in l:
			cnt = 10000000000000.0
			break
		l.append(k)
	ans = min(ans, cnt)
print(ans)


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
c = 1000000000000
f = [False] * n
for i in a:
	f[i - 1] = True
for j in range(1, n):
	b = list(f)
	x = 0
	y = 0
	z = 0
	while y != m and x < c:
		if b[z]:
			y += 1
			b[z] = False
		z = (z + j) % n
		x += 1
	if x < c:
		c = x
	if c == m:
		break
print(c)


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
maximum = 1000000000000
final = [False] * n
for i in a:
	final[i - 1] = True
for j in range(1, n):
	test = list(final)
	total = 0
	x = 0
	index = 0
	while x != m and total < maximum:
		if test[index]:
			x += 1
			test[index] = False
		index = (index + j) % n
		total += 1
	if total < maximum:
		maximum = total
	if maximum == m:
		break
print(maximum)


(hash, ans) = ({}, [])
(n, m) = map(int, input().split())
ka = set(list(map(int, input().split())))
for i in range(n + 1):
	(z, count, ba) = (1, 0, 0)
	while True:
		if z == 1 and count != 0:
			break
		if ba == m:
			break
		if z in ka:
			ba += 1
		if z + i <= n:
			z += i
		else:
			k = z + i
			z = k - n
		count += 1
	if ba == m:
		ans.append(count)
print(min(ans))


(n, m) = map(int, input().split())
ls = set(list(map(int, input().split())))
mn = 10 ** 9
for i in range(1, n):
	count = 0
	dct = {}
	s = 0
	k = m
	case = 1
	while k > 0:
		if s in dct:
			case = 0
			break
		dct[s] = 1
		if s + 1 in ls:
			k -= 1
		s = (s + i) % n
		count += 1
	if case:
		mn = min(mn, count)
print(mn)


try:
	(n, m) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr.sort()
	mindif = 999999
	maxdif = arr[-1] - arr[0]
	for i in range(1, m):
		if mindif > arr[i] - arr[i - 1]:
			mindif = arr[i] - arr[i - 1]
	minstop = []
	d = dict()
	d1 = dict()
	for i in range(mindif, maxdif + 1):
		for _ in arr:
			d[_] = 1
			d1[_] = 1
		count = 0
		stop = 0
		j = 1
		while j < n + 1:
			stop += 1
			if j == 1:
				count += 1
				if count == 2:
					stop = 99999999
					break
			if j in d:
				if d[j] == 1:
					d[j] = 0
					del d1[j]
				else:
					stop = 99999999
					break
			if len(d1) == 0:
				break
			j += i
			if j > n:
				j = j % n
		minstop += [stop]
	print(min(minstop))
except EOFError:
	pass


(n, m) = map(int, input().split())
l = list(map(int, input().split()))
e = {}
for i in range(m):
	e[l[i]] = 0
d = []
for i in range(1, n):
	k = []
	f = 0
	while len(k) != n:
		if len(k) == 0:
			c = 1
		else:
			c = (k[-1] + i) % n
		if c == 0:
			c = n
		k.append(c)
		try:
			g = e[k[-1]]
			if g == 0:
				f += 1
				e[k[-1]] = 1
			if f == m:
				d.append(len(k))
				break
		except:
			pass
	for i in range(m):
		e[l[i]] = 0
print(min(d))


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
mark = [-1 for x in range(n + 1)]
for i in range(m):
	mark[a[i]] = 0
minn = 10000
for i in range(1, n):
	pos = 1
	count = 0
	ans = 1
	while True:
		if mark[pos] != -1 and mark[pos] != i:
			mark[pos] = 0
			count += 1
		pos = (pos + i) % n
		if pos == 0:
			pos = n
		if pos == 1 or count == m:
			break
		ans += 1
	if count == m:
		minn = min(ans, minn)
print(minn)


ll = lambda : list(map(int, input().split()))
[n, x] = ll()
arr = ll()
h = [0] * n
minj = 9999999
for i in range(x):
	h[arr[i] - 1] = 1
for px in range(1, n - 1):
	vis = [0] * (n + 1)
	viscells = 0
	index = 0
	jumps = 0
	while viscells != x and vis[index] == 0:
		if h[index] == 1:
			viscells += 1
		vis[index] = 1
		index = (index + px) % n
		jumps += 1
	if viscells == x and jumps < minj:
		minj = jumps
print(minj)


(n, _) = [int(i) for i in input().split()]
arr = [int(i) for i in input().split()]
boo = [True if i in arr and i != 1 else False for i in range(1, n + 1)]
lis = [0] * n
ii = 1
for aa in range(1, n):
	i = 1
	boo1 = boo.copy()
	while True in boo1:
		boo1[i - 1] = False
		lis[aa - 1] += 1
		i = (i + aa) % n
		if lis[aa - 1] > 2000:
			break
	time = lis[aa - 1]
lis = lis[:-1]
print(min(lis))


(n, m) = map(int, input().split())
f = [[] * i for i in range(1001)]
for i in range(1001):
	for j in range(1001):
		f[i].append(-1)
for i in range(1, 1001):
	s = 0
	for x in range(1, 100000000, i):
		s = s + 1
		if s > 1005:
			break
		if x % n != 0:
			if f[i][x % n] == -1:
				f[i][x % n] = s
			else:
				f[i][x % n] = min(f[i][x % n], s)
		elif f[i][n] == -1:
			f[i][n] = s
		else:
			f[i][n] = min(f[i][n], s)
a = list(map(int, input().split()))
p = [100000000] * 1005
for i in range(1, 1001):
	try:
		for j in a:
			if f[i][j] == -1:
				s = 0 / 0
			if p[i] == 100000000:
				p[i] = f[i][j]
			else:
				p[i] = max(p[i], f[i][j])
	except:
		p[i] = 100000000
		continue
print(min(p))


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
ans = 999999999999
for x in range(1, n):
	s = set(a)
	stops = 0
	q = 1
	for i in range(n):
		if q in s:
			s.remove(q)
		q = (q - 1 + x) % n + 1
		stops += 1
		if len(s) == 0:
			break
	if len(s) == 0:
		ans = min(ans, stops)
print(ans)


def read():
	return input().strip()

def readint():
	return int(read())
(n, k) = map(int, read().split())
arr = [0] * 1001
for i in read().split():
	arr[int(i)] = 1
mink = 9999999
for i in range(1, n):
	brr = list(arr)
	s = k
	j = 1
	ii = 0
	val = 0
	while s > 0:
		val = j % n
		if val == 0:
			val = n
		if brr[val] == 0 and arr[val] == 1:
			ii = 9999999
			break
		if brr[val] == 1:
			s = s - 1
			brr[val] = 0
		j = j + i
		ii += 1
		if ii > mink:
			break
	if ii < mink:
		mink = ii
print(mink)


(n, m) = map(int, input().split())
l = set(map(int, input().split()))
arr = [i for i in range(1, n + 1)]
ans = 10 ** 9
x = 1
while x < n + 1:
	array = set()
	ind = [False] * n
	done = False
	array.add(1)
	val = 1
	cou = 1
	while not done:
		no = (val + x) % n
		if no == 0:
			no = n
		if no in array:
			break
		else:
			array.add(no)
			cou += 1
		val += x
		if cou == n:
			done = True
		if array >= l:
			if len(array) < ans:
				ans = len(array)
			break
	x += 1
print(ans)


from bisect import bisect_right as br
from bisect import bisect_left as bl
from collections import *
from itertools import *
import functools
import sys
import math
import random
import re
MAX = sys.maxsize
MAXN = 10 ** 5 + 10
MOD = 10 ** 9 + 9

def isprime(n):
	n = abs(int(n))
	if n < 2:
		return False
	if n == 2:
		return True
	if not n & 1:
		return False
	for x in range(3, int(n ** 0.5) + 1, 2):
		if n % x == 0:
			return False
	return True

def mhd(a, b, x, y):
	return abs(a - x) + abs(b - y)

def numIN(x=' '):
	return map(int, sys.stdin.readline().strip().split(x))

def charIN(x=' '):
	return sys.stdin.readline().strip().split(x)

def dis(x, y):
	a = y[0] - x[0]
	b = x[1] - y[1]
	return (a * a + b * b) ** 0.5

def lgcd(a):
	g = a[0]
	for i in range(1, len(a)):
		g = math.gcd(g, a[i])
	return g

def ms(a):
	msf = -MAX
	meh = 0
	for i in range(len(a)):
		meh += a[i]
		if msf < meh:
			msf = meh
		if meh < 0:
			meh = 0
	return msf
(n, m) = numIN()
a = list(numIN())
d = [0] * (n + 1)
for i in a:
	d[i] = 1
mn = MAX
for i in range(1, n + 1):
	x = 1
	cnt = 0
	if d[x]:
		cnt += 1
	fl = 1
	ans = 1
	f = [0] * (n + 1)
	while cnt != m:
		x += i
		ans += 1
		if x > n:
			x %= n
		f[x] += 1
		if f[x] > 1:
			fl = 0
			break
		if d[x]:
			cnt += 1
	if fl:
		mn = min(mn, ans)
print(mn)


(n, m) = map(int, input().split())
s = [int(i) for i in input().split()]
min_val = 10 ** 9 + 7
for x in range(1, n):
	c = [1001] * (n + 1)
	c[0] = 0
	for i in range(n + 1):
		val = (x * i + 1) % n
		if val == 0:
			val = n
		c[val] = min(c[val], i + 1)
	temp_val = 0
	for i in s:
		temp_val = max(temp_val, c[i])
	min_val = min(min_val, temp_val)
print(min_val)


from collections import defaultdict
(n, m) = map(int, input().split())
a = [int(j) for j in input().split()]
dic = defaultdict(int)
mi = 10 ** 10
for i in range(n):
	for x in a:
		dic[x] = 0
	count = 0
	anscount = 0
	ind = 0
	visited = [False] * n
	while True:
		if visited[ind] == True:
			break
		else:
			visited[ind] = True
			count += 1
		if ind + 1 in dic:
			if dic[ind + 1] == 0:
				dic[ind + 1] = 1
				anscount += 1
		if anscount == len(a):
			break
		ind += i + 1
		ind %= n
	var = 0
	for abc in dic:
		if dic[abc] == 0:
			var = 1
			break
	if count < mi and var == 0:
		mi = count
print(mi)


s = list(map(int, input().split()))
(n, m) = (s[0], s[1])
lol = list(map(int, input().split()))
dict = {}
for i in range(10001):
	dict[i] = 0
for i in range(len(lol)):
	dict[lol[i]] = 1
x = 1
minstop = 1000000007
while x < n:
	stop = 1
	nex = 1 + x
	l = []
	if dict[1] == 1:
		l.append(1)
	if len(l) == m:
		minstop = 1
		break
	while True:
		stop += 1
		if dict[nex] == 1:
			l.append(nex)
		if len(l) == m:
			break
		nex = nex + x
		if nex > n:
			nex = nex - n
		if nex == 1 and len(l) != m:
			stop = 1000000007
			break
	minstop = min(minstop, stop)
	x += 1
print(minstop)


(n, m) = map(int, input().split())
l = [int(i) for i in input().split()]
from collections import Counter
c = Counter(l)
ans = 10 ** 9
for x in range(1, n + 1):
	cnt = 1
	k = 0
	z = 1
	seen = 0
	if c[1]:
		seen = 1
		c[1] -= 1
	while cnt < n:
		z = (z + x) % n
		if z == 0:
			z = n
		if c[z]:
			seen += 1
			c[z] -= 1
		cnt += 1
		if seen == m:
			break
	c = Counter(l)
	if seen == m:
		if cnt < ans:
			ans = cnt
			ansx = x
print(ans)


def totient(n):
	ret = n
	i = 2
	while i * i <= n:
		if n % i == 0:
			ret = (i - 1) * (ret // i)
			while n % i == 0:
				n //= i
		i += 1
	if n:
		ret = (n - 1) * (ret // n)
	return ret

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def main():
	(n, m) = map(int, input().split())
	arr = list(map(int, input().split()))
	phi = totient(n)
	ans = 1000
	for i in range(1, n):
		tmp = 0
		g = gcd(i, n)
		if g != 1:
			for d in arr:
				if (d - 1) % g:
					tmp = -1
					break
		if tmp == -1:
			continue
		j = i // g
		for d in arr:
			tmp = max(tmp, (d - 1) // g * pow(j, phi - 1, n) % n)
		if tmp == 1:
			print(i)
		ans = min(ans, tmp + 1)
	print(ans)
	return 0
main()