extrapolation

Frau is sick of all those “find the next number” puzzles. She’s decided to write a program that solves this kind of task automatically. She’s come up with the following simple algorithm: Treat the known numbers as values of a real coefficient polynomial (with as small a degree as possible) on the first few positive integers, and then evaluate the next value as the function of this polynomial.

Unfortunately, even though Frau is proficient at both math and programming, she can’t handle them both at the same time. Help Frau write this program!

Example:

• For values = [2, 8, 14, 20], the output should be
  extrapolation(values) = 26.

  The values for x from 1 through 4can be calculated by the formula f(x) = 6x - 4. Thus, the next number is f(5) = 26.

• For values = [1, 3, 6, 10, 15], the output should be
  extrapolation(values) = 21.

  The perfect fitting polynomial is f(x) = (1/2)x2 + (1/2)x, so the next number is f(6) = 21.

• For values = [0, 1, 8, 34, 104, 259], the output should be
  extrapolation(values) = 560.

  The values fit the polynomial f(x) = (1/30)x5 - (1/30)x with x from 1 to 6, so the next number is f(7) = 560.

Input/Output

• [execution time limit] 0.5 seconds 

• [input] array.integer64 values

  The given first few numbers. values[i] is f(i + 1) for each valid i.
  1 ≤ values.length ≤ 40,
  -1000 ≤ values[i] ≤ 1000.

• [output] integer64

  The extrapolated next number. It is guaranteed that the answer is an integer with an absolute value of ≤ 2⁵².