Holidays#3211
In strange town Klahol, rabbits behave in a strange way. Everything is strange, even holidays. And the year somehow has days. The complexity is also that nobody except rabbits knows which day of the year is today. Days are numbered in a simple way: integers from to .
Derabbit Bryan came to the town. He was lucky to find a calendar with all holidays in this wonderful town. Altogether, there are holidays. Bryan is interested in the mean number of days till the closest coming holiday.
The first line contains two integers separated by a space: and (1 \le n \le 10^{9}, 1 \le m \le \min(10^{6},\ n)). The second line contains integers — day numbers for holidays (integers from to ).
You need to output the mean number of days till the closest holiday (derabbit can’t learn which day is today, he assumes each of the days is equally possible) as an irreducible fraction (see samples).
Example 1