Consider the following pseudocode, run on an array $A=[a_0,a_1,...,a_{n-1}]$ of length $n$:

rep := 0
while A not empty:
    B := []
    for x in A, y in A:
        if x != y: append absolute_value(x - y) to B
    A := B
    rep := rep + 1

Given the values of $n$ and array $\mbox{A}$, compute and print the final value of ${\mbox{rep}}$ after the pseudocode above terminates; if the loop will never terminate, print -1 instead.

Input Format

The first line contains a single integer, $n$, denoting the length of array $\mbox{A}$. 

The second line contains $n$ space-separated integers describing the respective values of $a_0,a_1,\ldots,a_{n-1}$.

Constraints

$1\leq n\leq10^5$  
$1\leq a_i\leq5\times10^4\ \text{}\forall\ 1\leq i\leq n$

Output Format

Print the final value of ${\mbox{rep}}$ after the pseudocode terminates; if the loop will never terminate, print -1 instead.

Sample Input 0
3
1 3 4

Sample Output 0
4

Explanation 0

After the first loop, $\mbox{A}$ becomes $[2,3,2,1,3,1]$. After the second loop, the array only contains $\mbox{1}$'s and $2$'s. After the third loop, the array only contains $\mbox{1}$'s. After the fourth loop, the array is empty. Because the value of ${\mbox{rep}}$ is incremented after each loop, $rep=4$ at the time the loop terminates. Thus, we print 4 as our answer.

Source: hackerrank | Difficulty: HARD
Tags: Bit manipulation


Solutions:
input()
A = set([int(m) for m in input().strip().split()])

def DeltaBasis2(AList, P=False):
	if type(AList) == set:
		AList = sorted(list(AList))
	if len(AList) == 1:
		return 1
	Count = 0
	while len(AList) > 0:
		if len(AList) == 1:
			return Count + 1
		LCM = True
		for i1 in AList[1:]:
			if i1 % AList[0] != 0:
				LCM = False
				break
		if LCM:
			AList = [int(m / AList[0]) for m in AList]
		if AList[0] == 1 and AList[1] == 2:
			return Count + AList[-1]
		Delta = set()
		if len(AList) < 100:
			MaxWidth = len(AList) - 1
		else:
			MaxWidth = int(len(AList) ** 0.75 // 1)
		for W in range(1, MaxWidth + 1):
			for i1 in range(len(AList) - W):
				Delta.add(abs(AList[i1 + W] - AList[i1]))
		Delta = sorted(list(Delta))
		AList = sorted(list(set([m for m in Delta] + [AList[-1] - m for m in AList[:-1]])))
		if P:
			print(AList2)
		Count += 1
	return Count
print(DeltaBasis2(A))