35133번 - Polynomially Constructed 다국어

You are given an integer $N$ and an array of integers $[y_1, y_2, \ldots, y_N]$ of size $N$.

You want to construct the following:

• a polynomial $P(x) = c_0 x^0 + c_1 x^1 + \ldots + c_d x^d$ where the coefficients are real numbers, and for some degree $d$;
• an array of real numbers $[x_1, x_2, \ldots, x_N]$ of size $N$ such that $x_1 < x_2 < \ldots < x_N$;

and the construction satisfies $P(x_1) = y_1$, $P(x_2) = y_2$, $\ldots$, $P(x_N) = y_N$.

It can be proven that such a construction always exists. Your task is to find the minimum polynomial degree $d$ that you can construct.

The first line contains an integer $N$ ($1 \leq N \leq 100000$). The second line contains $N$ integers representing $y_i$ ($-10^9 \leq y_i \leq 10^9$).

Output the minimum degree $d$ in a single line.

Explanation of Sample 1: We can construct a polynomial $\frac{29}{3} x^0 + 8x^1 + 0 x^2 - \frac{2}{3} x^3$, and array $[-2.81273..., -2, -1.24361..., 3.86937..., 3.91423...]$.