Description

As stated, you are given an $N$-th degree polynomial. It is guaranteed that within the interval $[l, r]$ there exists a point $x$ such that the function is monotonically increasing on $[l, x]$ and monotonically decreasing on $[x, r]$. Find the value of $x$.

Input Format

The first line contains a positive integer $N$ and two real numbers $l, r$, as described above.

The second line contains $N + 1$ real numbers, representing the coefficients of the $N$-th degree polynomial from highest degree to lowest.

Output Format

Output one line containing a real number, which is the value of $x$. Your answer is considered correct if it satisfies either of the following:

• Your answer $x'$ has a relative or absolute error not exceeding $10^{-5}$ compared to the standard answer $x$.
• The function values corresponding to your answer and the standard answer, that is, $f(x')$ and $f(x)$, have a relative or absolute error not exceeding $10^{-5}$.

3 -0.9981 0.5
1 -3 -3 1

-0.41421

Hint

For $100\%$ of the testdata, $6 \le N \le 13$, the coefficients of the polynomial are in $[-100, 100]$ with up to $15$ decimal places, $|l|, |r| \le 10$ with up to $15$ decimal places, and $l \le r$.

Sample Explanation:

As shown in the figure, the red segment is the graph of the function $f(x) = x^3 - 3 x^2 - 3x + 1$ on the interval $[-0.9981, 0.5]$.

When $x = -0.41421$, the graph reaches its highest point, so the function is monotonically increasing on $[l, x]$ and monotonically decreasing on $[x, r]$. Therefore $x = -0.41421$, and the output is $-0.41421$.

Translated by ChatGPT 5