Question
Range Trim
Kael has an array B of M integers. He can perform the following move on each index j (0 to M-1) at most once:
- if Bj > 1, select a prime divisor of Bj and either add or subtract it from Bj.
Input
The first line of the input contains an integer M - the size of array B
The next line of the input contains M space-separated integers B0, B1,. . BN-1
Constraints
1 ≤ M ≤ 105
1 ≤ Bi ≤ 106
The next line of the input contains M space-separated integers B0, B1,. . BN-1
Constraints
1 ≤ M ≤ 105
1 ≤ Bi ≤ 106
Output
Print the minimised difference you can achieve after applying the above operations any number of times.
Example
Sample Input
5
17 5 22 18 9
Sample Output
7
Explanation
Apply no operation on 17.
Add 5 (prime divisor of 5) to 5, making it 10.
Subtract 11 (prime divisor of 22) from 22, making it 11.
Subtract 2 (prime divisor of 18) from 18, making it 16.
Add 3 (prime divisor of 9) to 9, making it 12.
Final array = [17, 10, 11, 16, 12]
Difference between the maximum and minimum is 7.
It can be proved that this difference cannot be minimised further.
5
17 5 22 18 9
Sample Output
7
Explanation
Apply no operation on 17.
Add 5 (prime divisor of 5) to 5, making it 10.
Subtract 11 (prime divisor of 22) from 22, making it 11.
Subtract 2 (prime divisor of 18) from 18, making it 16.
Add 3 (prime divisor of 9) to 9, making it 12.
Final array = [17, 10, 11, 16, 12]
Difference between the maximum and minimum is 7.
It can be proved that this difference cannot be minimised further.