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.

Difficulty: interview

Starter code:

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])

# cook your code here
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))

# cook your code here
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)