Find the Peak of a Unimodal Polynomial Function

Given an \(N\)th-degree polynomial function defined as
\( f(x)=a_Nx^N+a_{N-1}x^{N-1}+\cdots+a_0 \),
and an interval \([l, r]\) such that there exists a point \(x\) which satisfies:

• The function is monotonically increasing on \([l, x]\), i.e., \(f(l) \le f(x') \le f(x)\) for all \(x' \in [l,x]\).
• The function is monotonically decreasing on \([x, r]\), i.e., \(f(x) \ge f(x'') \ge f(r)\) for all \(x'' \in [x,r]\).

This guarantees that \(x\) is the unique maximizer of \(f(x)\) on \([l, r]\). Find the value of \(x\) where \(f(x)\) attains its maximum. Your answer should be computed to 6 decimal places. It is recommended to use a numerical method such as ternary search because an analytical solution may not be feasible for high-degree polynomials.

inputFormat

The input consists of two lines:

1. The first line contains three numbers: an integer \(N\) (the degree of the polynomial) and two real numbers \(l\) and \(r\) representing the endpoints of the interval \([l, r]\).
2. The second line contains \(N+1\) real numbers representing the coefficients \(a_N, a_{N-1}, \dots, a_0\) of the polynomial in descending order.

outputFormat

Output a single real number: the value of \(x\) where \(f(x)\) achieves its maximum in the interval \([l, r]\), rounded to exactly 6 decimal places.

sample

2 0 2
-1 2 1

1.000000