The Calculus of Ada

Augusta Ada King-Noel, Countess of Lovelace, is best known for the programs she wrote for Charles Babbage's Analytical Engine. She also described how the method of finite differences solves problems about number sequences and series, and Babbage's Difference Engine implemented those techniques.

The method works like this. Take the difference between each pair of consecutive values in a numeric sequence. The sequence you get is related to the derivative of the function behind the original sequence. When the original sequence comes from a first-degree polynomial (a linear function), the first differences are all the same value, a constant. When it comes from a second-degree polynomial, the first differences change linearly, so the differences of that new sequence, the second differences, are constant. The same rule continues for higher degrees: for a polynomial of degree $n$, the $n$-th row of differences is constant.

For example, the first-degree polynomial $3x + 3$ evaluated at $x = 0, 1, 2, 3, 4$ gives the table below.

The polynomial $x^2$ evaluated at $x = 3, 5, 7, 9$ gives this table.

Once a row of differences is constant, you can extend the table one column to the right and read off the value that a minimal-degree polynomial takes at the next regularly spaced input.

You are given the values of a polynomial at $n$ regularly spaced inputs. Report the degree of a minimal-degree polynomial that produces those values, together with the value that same polynomial takes at the next regularly spaced input.

The input contains an integer $n$ ($2 \le n \le 10$), the number of polynomial values given, followed by $n$ integers $v_1, v_2, \dots, v_n$, the values of a polynomial evaluated at $n$ regularly spaced inputs. Every $v_j$ satisfies $-2\,000\,000 \le v_j \le 2\,000\,000$, and at least two of the given values differ from each other. The numbers are separated by whitespace, so they may sit on one line or on several.

Print two integers $d$ and $v_{n+1}$ separated by one space. The value $d$ is the degree of a minimal-degree polynomial that produces the given sequence, and $v_{n+1}$ is the value of that polynomial at the next regularly spaced input. Since at least two of the given values differ, $d$ is between 1 and $n - 1$, and both answers are unique.