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: HARD
Tags: Sorting

Amortized analysis

Mathematics
Skill types: Sorting

Amortized analysis

Starter code:

Solutions:
def main():
	input()
	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)
main()


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


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)


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


import os, sys
from io import BytesIO, IOBase

def main():
	n = int(input())
	a = sorted(map(int, input().split()))
	X = max(a)
	arr = [0] * (X + 1)
	arr1 = [0] * (X + 1)
	j = a[0] + 1
	for i in range(n - 1):
		while j <= a[i + 1]:
			arr1[j] = a[i]
			j += 1
	ans = 0
	for i in range(n):
		if not arr[a[i]]:
			arr[a[i]] = 1
			for x in range(2 * a[i], X + 1, a[i]):
				ans = max(ans, arr1[x] % a[i])
			ans = max(ans, a[-1] % a[i])
	print(ans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


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)
main()


import sys
input = sys.stdin.readline
t = 1
while t:
	t -= 1
	n = int(input())
	a = sorted(list(set(map(int, input().split()))))
	m = 2 * a[-1]
	prev = [0] * (m + 1)
	ans = 0
	j = 0
	for el in a:
		prev[el + 1] = el
	for i in range(1, len(prev)):
		if not prev[i]:
			prev[i] = prev[i - 1]
	for el in a:
		k = 2
		while k * el <= m:
			ans = max(ans, prev[k * el] % el)
			k += 1
	print(ans)


import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
a = sorted(list(set(a)))
mx = max(a)
b = [0] * (2 * mx)
for aa in a:
	b[aa] = aa
for i in range(1, len(b)):
	if b[i] == 0:
		b[i] = b[i - 1]
ans = 0
for aa in a:
	for m in range(2 * aa, 2 * mx, aa):
		if b[m - 1] >= aa:
			ans = max(ans, b[m - 1] % aa)
print(ans)


import collections
import time
import os
import sys
import bisect
import heapq
from typing import List

def solve(A):
	A = list(sorted(set(A)))
	ma = 2 * max(A)
	leftmax = [0 for i in range(ma + 1)]
	for v in A:
		leftmax[v] = v
	v = 0
	for i in range(ma + 1):
		nv = max(v, leftmax[i])
		leftmax[i] = v
		v = nv
	ans = 0
	for v in A:
		k = 2
		while k * v <= ma:
			u = k * v
			w = leftmax[u]
			ans = max(ans, w % v)
			k += 1
	return ans
N = int(input())
A = [int(x) for x in input().split()]
print(solve(A))


n = int(input())
l = list(map(int, input().split(' ')))
l = list(set(l))
lb = [-1] * 3000001
for i in l:
	lb[i + 1] = i
for i in range(1, 3000001):
	if lb[i] == -1:
		lb[i] = lb[i - 1]
ans = 0
maxi = 2 * l[-1]
for i in l:
	x = 2 * i
	while x <= maxi:
		ans = max(ans, lb[x] % i)
		x += i
	ans = max(ans, lb[x] % i)
print(ans)


import math
from bisect import bisect_right, bisect_left
from heapq import heappop, heappush
from itertools import accumulate
R = lambda : map(int, input().split())
n = int(input())
nums = set(R())
mn = max(nums)
arr = [0] * (mn + 1)
for x in nums:
	arr[x] = x
for i in range(1, len(arr)):
	arr[i] = arr[i - 1] if not arr[i] else arr[i]
res = 0
for x in nums:
	tmp = x
	while tmp <= mn:
		res = max(res, arr[tmp] % x, arr[tmp - 1] % x if arr[tmp - 1] > x else 0)
		tmp += x
	if x + 1 < len(arr):
		res = max(res, arr[x + 1] % x, mn % x)
print(res)


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)


R = lambda : map(int, input().split())
n = int(input())
nums = set(R())
mn = max(nums)
arr = [0] * (mn + 1)
for x in nums:
	arr[x] = x
for i in range(1, len(arr)):
	arr[i] = arr[i - 1] if not arr[i] else arr[i]
res = 0
for x in nums:
	tmp = 2 * x
	while tmp <= mn:
		res = max(res, arr[tmp - 1] % x if arr[tmp - 1] > x else 0)
		tmp += x
	if x + 1 < len(arr):
		res = max(res, mn % x)
print(res)


n = int(input())
a = list(set(map(int, input().split())))
mx = max(a)
b = [0] * (2 * mx)
for e in a:
	b[e] = e
for i in range(1, len(b)):
	if b[i] == 0:
		b[i] = b[i - 1]
best = 0
for e in a:
	for m in range(2 * e, 2 * mx, e):
		if b[m - 1] >= e:
			best = max(best, b[m - 1] % e)
print(best)


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)


import os
import sys
from io import BytesIO, IOBase
import heapq as h
import bisect
from types import GeneratorType
BUFSIZE = 8192

class SortedList:

	def __init__(self, iterable=[], _load=200):
		values = sorted(iterable)
		self._len = _len = len(values)
		self._load = _load
		self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
		self._list_lens = [len(_list) for _list in _lists]
		self._mins = [_list[0] for _list in _lists]
		self._fen_tree = []
		self._rebuild = True

	def _fen_build(self):
		self._fen_tree[:] = self._list_lens
		_fen_tree = self._fen_tree
		for i in range(len(_fen_tree)):
			if i | i + 1 < len(_fen_tree):
				_fen_tree[i | i + 1] += _fen_tree[i]
		self._rebuild = False

	def _fen_update(self, index, value):
		if not self._rebuild:
			_fen_tree = self._fen_tree
			while index < len(_fen_tree):
				_fen_tree[index] += value
				index |= index + 1

	def _fen_query(self, end):
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		x = 0
		while end:
			x += _fen_tree[end - 1]
			end &= end - 1
		return x

	def _fen_findkth(self, k):
		_list_lens = self._list_lens
		if k < _list_lens[0]:
			return (0, k)
		if k >= self._len - _list_lens[-1]:
			return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		idx = -1
		for d in reversed(range(len(_fen_tree).bit_length())):
			right_idx = idx + (1 << d)
			if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
				idx = right_idx
				k -= _fen_tree[idx]
		return (idx + 1, k)

	def _delete(self, pos, idx):
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len -= 1
		self._fen_update(pos, -1)
		del _lists[pos][idx]
		_list_lens[pos] -= 1
		if _list_lens[pos]:
			_mins[pos] = _lists[pos][0]
		else:
			del _lists[pos]
			del _list_lens[pos]
			del _mins[pos]
			self._rebuild = True

	def _loc_left(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(lo, pos) = (-1, len(_lists) - 1)
		while lo + 1 < pos:
			mi = lo + pos >> 1
			if value <= _mins[mi]:
				pos = mi
			else:
				lo = mi
		if pos and value <= _lists[pos - 1][-1]:
			pos -= 1
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value <= _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def _loc_right(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(pos, hi) = (0, len(_lists))
		while pos + 1 < hi:
			mi = pos + hi >> 1
			if value < _mins[mi]:
				hi = mi
			else:
				pos = mi
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value < _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def add(self, value):
		_load = self._load
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len += 1
		if _lists:
			(pos, idx) = self._loc_right(value)
			self._fen_update(pos, 1)
			_list = _lists[pos]
			_list.insert(idx, value)
			_list_lens[pos] += 1
			_mins[pos] = _list[0]
			if _load + _load < len(_list):
				_lists.insert(pos + 1, _list[_load:])
				_list_lens.insert(pos + 1, len(_list) - _load)
				_mins.insert(pos + 1, _list[_load])
				_list_lens[pos] = _load
				del _list[_load:]
				self._rebuild = True
		else:
			_lists.append([value])
			_mins.append(value)
			_list_lens.append(1)
			self._rebuild = True

	def discard(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_right(value)
			if idx and _lists[pos][idx - 1] == value:
				self._delete(pos, idx - 1)

	def remove(self, value):
		_len = self._len
		self.discard(value)
		if _len == self._len:
			raise ValueError('{0!r} not in list'.format(value))

	def pop(self, index=-1):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		value = self._lists[pos][idx]
		self._delete(pos, idx)
		return value

	def bisect_left(self, value):
		(pos, idx) = self._loc_left(value)
		return self._fen_query(pos) + idx

	def bisect_right(self, value):
		(pos, idx) = self._loc_right(value)
		return self._fen_query(pos) + idx

	def count(self, value):
		return self.bisect_right(value) - self.bisect_left(value)

	def __len__(self):
		return self._len

	def __getitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		return self._lists[pos][idx]

	def __delitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		self._delete(pos, idx)

	def __contains__(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_left(value)
			return idx < len(_lists[pos]) and _lists[pos][idx] == value
		return False

	def __iter__(self):
		return (value for _list in self._lists for value in _list)

	def __reversed__(self):
		return (value for _list in reversed(self._lists) for value in reversed(_list))

	def __repr__(self):
		return 'SortedList({0})'.format(list(self))

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
import collections as col
import math, string

def getInts():
	return [int(s) for s in input().split()]

def getInt():
	return int(input())

def getStrs():
	return [s for s in input().split()]

def getStr():
	return input()

def listStr():
	return list(input())
MOD = 10 ** 9 + 7
t = 1
p = 10 ** 9 + 7

def ncr_util():
	inv[0] = inv[1] = 1
	fact[0] = fact[1] = 1
	for i in range(2, 300001):
		inv[i] = inv[i % p] * (p - p // i) % p
	for i in range(1, 300001):
		inv[i] = inv[i - 1] * inv[i] % p
		fact[i] = fact[i - 1] * i % p

def solve():
	(ans, ind) = (0, -1)
	MAXN = 2 * 10 ** 6 + 2
	l1 = [-1] * (2 * 10 ** 6 + 2)
	for i in l:
		l1[i + 1] = i
	l1[0] = 0
	for i in range(1, MAXN):
		if l1[i] == -1:
			l1[i] = l1[i - 1]
	maxi = 2 * max(l)
	for i in range(len(l)):
		m = 2
		j = l[i] * 2
		while j <= maxi:
			ans = max(l1[j] % l[i], ans)
			j += l[i]
	return ans
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	l = list(set(l))
	l.sort()
	print(solve())


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