You have an array A of size N containing only positive numbers. You have to output the maximum possible value of A[i]%A[j] where 1<=i,j<=N. 

-----Input-----
The first line of each test case contains a single integer N denoting the size of the array. The next N lines contains integers A1, A2, ..., AN denoting the numbers

-----Output-----
Output a single integer answering what is asked in the problem.

-----Subtask 1 (20 points)-----
- 1 ≤ N ≤ 5000
- 1 ≤ A[i] ≤ 2*(10^9)

-----Subtask 2 (80 points)-----
- 1 ≤ N ≤ 1000000
- 1 ≤ A[i] ≤ 2*(10^9)

-----Example-----
Input:
2
1
2

Output:
1

-----Explanation-----
There will be four values, A[0]%A[0] = 0, A[0]%A[1]=1, A[1]%A[0]=0, A[1]%A[1]=0, and hence the output will be the maximum among them all, that is 1.

Source: codechef | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
n = int(input())
a = []
for i in range(n):
	a.append(int(input()))
m1 = 0
m2 = 0
for e in a:
	if e > m1:
		m2 = m1
		m1 = e
	elif e > m2 and e != m1:
		m2 = e
ans = 0
for e in a:
	temp = m1 % e
	if temp > ans:
		ans = temp
print(max(m2 % m1, ans))


__author__ = 'Hacktivist'
from sys import stdin
lst = list()
testCase = int(stdin.readline().strip())
for test in range(testCase):
	lst.append(int(stdin.readline().strip()))
lst.sort()
if len(lst) <= 5000:
	maximum = 0
	for i in range(len(lst)):
		for j in range(len(lst)):
			if lst[i] % lst[j] > maximum:
				maximum = lst[i] % lst[j]
	print(maximum)
else:
	print(lst[len(lst) - 2] % lst[len(lst) - 1])


N = int(input())
A = {}
largest = 0
for m in range(0, N):
	p = int(input())
	A[p] = 0
for k in A:
	for m in A:
		if k % m > largest:
			largest = k % m
print(largest)


n = int(input())
a = sorted(set([int(input()) for _ in range(n)]))
print(0 if len(a) < 2 else a[-2])


N = eval(input())
A = []
for _ in range(N):
	A += [eval(input())]
B = [0]
A.sort()
for i in range(N):
	for j in range(i + 1, N):
		B += [A[i] % A[j]] + [A[j] % A[i]]
print(max(B))


N = eval(input())
A = []
for _ in range(N):
	A += [eval(input())]
B = []
for i in A:
	for j in A:
		B += [i % j]
print(max(B))


size = int(input())
array = []
for x in range(size):
	array.append(int(input()))
diff = 0
if size < 1600:
	for i in range(size):
		for j in range(i + 1, size):
			if array[i] % array[j] > diff:
				diff = array[i] % array[j]
else:
	m1 = max(array)
	array.pop(array.index(m1))
	m2 = max(array)
	diff = m2 % m1
print(diff)


size = int(input())
array = []
for x in range(size):
	array.append(int(input()))
diff = 0
for i in range(size):
	for j in range(i + 1, size):
		if array[i] % array[j] > diff:
			diff = array[i] % array[j]
print(diff)