game-of-sweets-icpc-10

Two kids are playing the following game: there are initially N cards and there is a non-negative integer written on the each card. They perform three steps:
The first player picks random card of the given N cards. Let's denote the number written on it as A. 
The second player picks random card of the other N - 1 cards. Let's  denote the number written on it as B.
If A equals B then, the game ends with a draw and nobody receives candies. Otherwise the game is finished. The kid with the greatest number is claimed as the winner and he gets |B - A| sweets.

You were watching your little son playing this game and noticed that there are not many outcomes  of the game. So now you are interested in the following question: how many different values of |A-B| are possible?

Input
The first line contains one integer N.
The second line contains N non-negative integers - numbers written on cards.

Output
Output the one number - answer to the question.

Constraints
2 ≤ N ≤ 10^5
0 ≤ A[i] ≤ 10^5

SAMPLE INPUT
3
4 8 6

SAMPLE OUTPUT
2

Explanation

The winner can get 2 sweets if the chosen cards were 6 and 8 (or 4 and 6). He also can get 4 sweets if the numbers on the cards were 4 and 8.

Source: hackerearth | Difficulty: HARD


Solutions: