Background

This problem may have severe precision issues and can be hard to pass on some testdata. The testdata is relatively weak and is for reference only.

Problem 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