You are given a sequence a consisting of n integers. Find the maximum possible value of $a_{i} \operatorname{mod} a_{j}$ (integer remainder of a_{i} divided by a_{j}), where 1 ≤ i, j ≤ n and a_{i} ≥ a_{j}.


-----Input-----

The first line contains integer n — the length of the sequence (1 ≤ n ≤ 2·10^5). 

The second line contains n space-separated integers a_{i} (1 ≤ a_{i} ≤ 10^6).


-----Output-----

Print the answer to the problem.


-----Examples-----
Input
3
3 4 5

Output
2

Difficulty: competition

Starter code:

Solutions:
def main():
    input()
    aa = sorted(map(int, input().split()))
    maxa = max(aa)
    m = [False] * (maxa + 1)
    x = []
    b = 0
    for a in aa:
        if b != a:
            m[a] = True
            for i in range(b, a):
                x.append(b)
            b = a
    x.append(b)
    ans = 0
    for i in range(maxa - 1, 1, -1):
        if i < ans:
            break
        if m[i]:
            for j in range(1, maxa // i + 1):
                ans = max(ans, x[min(i * (j + 1) - 1, maxa)] % i)
    print(ans)


def __starting_point():
    main()
__starting_point()

def main():
    input()
    aa = sorted(map(int, input().split()))
    maxa = aa[-1]
    m = [False] * (maxa + 1)
    x = []
    b = res = 0
    for a in aa:
        if b != a:
            m[a] = True
            for i in range(b, a):
                x.append(b)
            b = a
    x.append(b)
    for a in range(maxa - 1, 1, -1):
        if a < res:
            break
        if m[a]:
            for b in range(2 * a - 1, maxa + 2 * a, a):
                res = max(res, x[min(b, maxa)] % a)
    print(res)


def __starting_point():
    main()
__starting_point()

def main():
    input()
    aa = sorted(set(map(int, input().split())))
    x = []
    b = res = 0
    for a in aa:
        if b != a:
            for _ in range(b, a):
                x.append(b)
            b = a
    x.append(b)
    maxa = aa.pop()
    for a in reversed(aa):
        if a < res:
            break
        for b in range(2 * a - 1, maxa + 2 * a, a):
            res = max(res, x[min(b, maxa)] % a)
    print(res)


def __starting_point():
    main()
__starting_point()

def main():
    input()
    #aa = sorted(set(map(int, input().split())))
    aa = sorted(map(int, set(input().split())))
    x = []
    b = res = 0
    for a in aa:
        if b != a:
            for _ in range(b, a):
                x.append(b)
            b = a
    x.append(b)
    maxa = aa.pop()
    for a in reversed(aa):
        if a < res:
            break
        for b in range(2 * a - 1, maxa + 2 * a, a):
            res = max(res, x[min(b, maxa)] % a)
    print(res)


def __starting_point():
    main()
__starting_point()

def main():
    input()
    aa = sorted(set(map(int, input().split())))
    x = []
    b = res = 0
    for a in aa:
        for _ in range(b, a):
            x.append(b)
        b = a
    x.append(b)
    maxa = aa.pop()
    for a in reversed(aa):
        if a < res:
            break
        for b in range(2 * a - 1, maxa + 2 * a, a):
            res = max(res, x[min(b, maxa)] % a)
    print(res)


def __starting_point():
    main()
__starting_point()

def main():
    input()
    aa = sorted(set(map(int, input().split())))
    x = []
    b = res = 0
    for a in aa:
        x += [b] * (a - b)
        b = a
    x.append(b)
    maxa = aa.pop()
    for a in reversed(aa):
        if a < res:
            break
        for b in range(2 * a - 1, maxa + 2 * a, a):
            res = max(res, x[min(b, maxa)] % a)
    print(res)


def __starting_point():
    main()
__starting_point()

def main():
    input()
    aa = sorted(set(map(int, input().split())))
    x = []
    b = res = 0
    for a in aa:
        x += [b] * (a - b)
        b = a
    x.append(b)
    maxa = aa.pop()
    for a in reversed(aa):
        if a < res:
            break
        for b in range(2 * a - 1, maxa, a):
            res = max(res, x[b] % a)
        res = max(res, maxa % a)
    print(res)


def __starting_point():
    main()
__starting_point()

def main():
    input()
    aa = sorted(set(map(int, input().split())))
    x = []
    b = res = 0
    for a in aa:
        x += [b] * (a - b)
        b = a
    x.append(b)
    maxa = aa.pop()
    for a in reversed(aa):
        if a < res:
            break
        res = max(res, maxa % a, *[b % a for b in x[2 * a - 1::a]])
    print(res)


def __starting_point():
    main()
__starting_point()

def main():
    input()
    aa = sorted(set(map(int, input().split())))
    x = []
    b = res = 0
    for a in aa:
        x += [b] * (a - b)
        b = a
    x.append(b)
    maxa = aa.pop()
    for a in reversed(aa):
        if a <= res:
            break
        res = max(res, maxa % a, *(b % a for b in x[2 * a - 1::a]))
    print(res)


def __starting_point():
    main()
__starting_point()

def main():
    input()
    aa = sorted(set(map(int, input().split())))
    x = []
    b = res = 0
    for a in aa:
        x += [b] * (a - b)
        b = a
    x.append(b)
    maxa = aa.pop()
    for a in reversed(aa):
        if a <= res:
            break
        res = max(res, maxa % a, *tuple(b % a for b in x[2 * a - 1::a]))
    print(res)


def __starting_point():
    main()
__starting_point()

def main():
    input()
    aa = sorted(set(map(int, input().split())))
    x = []
    b = res = 0
    for a in aa:
        x += [b] * (a - b)
        b = a
    x.append(b)
    maxa = aa.pop()
    for a in reversed(aa):
        if a <= res:
            break
        res = max(res, maxa % a, *[b % a for b in x[2 * a - 1::a]])
    print(res)


def __starting_point():
    main()
__starting_point()

input()
aa = sorted(set(map(int, input().split())))
x = []
b = res = 0
for a in aa:
    x += [b] * (a - b)
    b = a
x.append(b)
maxa = aa.pop()
for a in reversed(aa):
    if a < res:
        break
    res = max(res, maxa % a, *[b % a for b in x[2 * a - 1::a]])
print(res)


n = int(input())
a = list(set(map(int,input().split())))
prev = [0] * 2000001
for x in a:
	prev[x] = x
latest = 0
for x in range(2000001):
	if prev[x] == x:
		prev[x] = latest
		latest = x
	else:
		prev[x] = latest
ans = 0	
for x in a:
	for j in range(2 * x, 2000001, x):
		ans = max(ans, prev[j] % x)
print (ans)

N = 2000001
n = int(input())
a = list(set(map(int,input().split())))
prev = [0] * N
for x in a:
	prev[x] = x
for x in range(N):
	prev[x] = max(prev[x], prev[x - 1])
ans = 0	
for x in a:
	for j in range(2 * x, N, x):
		ans = max(ans, prev[j - 1] % x)
print (ans)

n = int(input())
a = sorted(list(set(map(int, input().split()))))
n = len(a)

lb = [0] + [-1] * 2000000
for x in a: lb[x] = x
for i in range(1,2000001):
  if (lb[i] == -1): lb[i] = lb[i-1]

ans = 0
for i in range(n):
  for j in range(2,2000000):
    if (a[i]*j > 1000000):
      ans = max(ans, a[-1] % a[i])
      break
    else: ans = max(ans, lb[j*a[i]-1] % a[i])
print(ans)



input()
s = sorted(set(map(int, input().split())))
c = m = 0
d = []
for b in s:
    d += [c] * (b - c)
    c = b
for b in s[-1::-1]:
    if b < m + 2: break
    m = max(m, c % b, *(a % b for a in d[2 * b - 1::b]))
print(m)

input()
d = [0] * 2000000
for k in map(int, input().split()): d[k] = 1
for i in range(len(d)): d[i] = i if d[i] else d[i - 1]
m = 0
for i in range(999999, 0, -1):
    if d[i] == i and i > m + 1: m = max(m, max(j % i for j in d[2 * i - 1::i]))
print(m)

input()
s = sorted(set(map(int, input().split())))
c = m = 0
d = []
for b in s:
    d += [c] * (b - c)
    c = b
for b in s[-1::-1]:
    if b < m + 2: break
    m = max(m, c % b, *(a % b for a in d[2 * b - 1::b]))
print(m)

input()
s = sorted(set(map(int, input().split())))
c = m = 0
d = []
for b in s:
    d += [c] * (b - c)
    c = b
for b in s[-1::-1]:
    if b < m + 2: break
    m = max(m, c % b, *(a % b for a in d[2 * b - 1::b]))
print(m)


input()
s = sorted(set(map(int, input().split())))
c = m = 0
d = []
for b in s:
    d += [c] * (b - c)
    c = b
for b in s[-1::-1]:
    if b < m + 2: break
    m = max(m, c % b, *(a % b for a in d[2 * b - 1::b]))
print(m)


input()
s = sorted(set(map(int, input().split())))
c = m = 0
d = []
for b in s:
    d += [c] * (b - c)
    c = b
for b in s[-1::-1]:
    if b < m + 2: break
    m = max(m, c % b, *(a % b for a in d[2 * b - 1::b]))
print(m)


input()
s = sorted(set(map(int, input().split())))
c = m = 0
d = []
for b in s:
    d += [c] * (b - c)
    c = b
for b in s[-1::-1]:
    if b < m + 2: break
    m = max(m, c % b, *(a % b for a in d[2 * b - 1::b]))
print(m)


input()
s = sorted(set(map(int, input().split())))
c = m = 0
d = []
for b in s:
    d += [c] * (b - c)
    c = b
for b in s[-1::-1]:
    if b < m + 2: break
    m = max(m, c % b, *(a % b for a in d[2 * b - 1::b]))
print(m)


input()
s = sorted(set(map(int, input().split())))
c = m = 0
d = []
for b in s:
    d += [c] * (b - c)
    c = b
for b in s[-1::-1]:
    if b < m + 2: break
    m = max(m, c % b, *(a % b for a in d[2 * b - 1::b]))
print(m)


input()
s = sorted(set(map(int, input().split())))
c = m = 0
d = []
for b in s:
    d += [c] * (b - c)
    c = b
for b in s[-1::-1]:
    if b < m + 2: break
    m = max(m, c % b, *(a % b for a in d[2 * b - 1::b]))
print(m)