B. Add Points

Codeforces

IDCF926B

Time1000ms

Memory256MB

Difficulty—

mathnumber theory

There are _n_ points on a straight line, and the _i_\-th point among them is located at _x__i_. All these coordinates are distinct. Determine the number _m_ — the smallest number of points you should add on the line to make the distances between all neighboring points equal. ## Input The first line contains a single integer _n_ (3 ≤ _n_ ≤ 100 000) — the number of points. The second line contains a sequence of integers _x_1, _x_2, ..., _x__n_ ( - 109 ≤ _x__i_ ≤ 109) — the coordinates of the points. All these coordinates are distinct. The points can be given in an arbitrary order. ## Output Print a single integer _m_ — the smallest number of points you should add on the line to make the distances between all neighboring points equal. [samples] ## Note In the first example you can add one point with coordinate 0. In the second example the distances between all neighboring points are already equal, so you shouldn't add anything.

Samples

Input #1

3
-5 10 5

Output #1

Input #2

6
100 200 400 300 600 500

Output #2

Input #3

4
10 9 0 -1

Output #3

API Response (JSON)

{
  "problem": {
    "name": "B. Add Points",
    "description": {
      "content": "There are _n_ points on a straight line, and the _i_\\-th point among them is located at _x__i_. All these coordinates are distinct. Determine the number _m_ — the smallest number of points you should",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF926B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "There are _n_ points on a straight line, and the _i_\\-th point among them is located at _x__i_. All these coordinates are distinct.\n\nDetermine the number _m_ — the smallest number of points you should...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments