Array

면접 대비

시간 제한3초메모리 제한256 MB

요약

배열을 임의로 재배열해 x = x mod a_i를 반복한 뒤 얻을 수 있는 마지막 값의 최댓값을 구한다.

문제

You are given an array $a\_1, a\_2, \ldots, a\_n$ . Let $x\_1 = a\_1$ , and $x\_i = x\_{i - 1} \bmod a\_i$ for each $i$ from $2$ to $n$ .

Suppose that we can rearrange $a\_1, \ldots, a\_n$ in any way. What is the largest possible value of $x\_n$ we can obtain?

The first line contains an integer $n$ --- the size of the array ( $2\leq n\leq 10^5$ ).

The second line containing $n$ integers $a\_1, \ldots, a\_n$ ( $1\leq a\_i\leq 10^5$ ).

Print one integer --- the largest possible value of $x\_n$ .