Cruel Math Teacher, II

As if raising numbers to powers were not cruel enough, Bessie's cruel math teacher has invented an even crueler assignment: find a root (a zero) of a polynomial.

Every such polynomial has an odd highest degree $D$ ($1 \le D \le 11$) and has exactly one real solution in the range $-1{,}000{,}000 \le X \le 1{,}000{,}000$; at that solution the polynomial evaluates to a value that is very close to (or exactly) $0$ in floating-point arithmetic.

Given a polynomial with real coefficients ($-500 \le coef_i \le 500$), find a value of $X$ that lies within $0.0005$ of the true root. Multiply that value of $X$ by $1{,}000$ and print it as a truncated (non-rounded) integer, discarding the fractional part toward zero.

For example, consider the cubic $1.5 \cdot x^3 - 10 = 0$. Its solution satisfies $x^3 = 100/15 = 20/3 = 6.6666\ldots$, so $x = 1.88207\ldots$; the correct output is therefore $1882$.

The polynomial is $\sum_{i=0}^{D} coef_i \cdot x^i$, where $x^i$ means $x$ raised to the $i$-th power.

No answer requires more than six significant digits, and every answer is small enough that it can be incremented by $0.0001$ in double-precision floating point without a serious loss of precision.

Hint: choose each new guess for $X$ so that the search interval shrinks at every step.

• Line 1: a single integer $D$.
• Lines 2 to $D+2$: line $i+2$ contains a single real number $coef_i$ (for $i = 0, 1, \ldots, D$).

• Line 1: a single integer — the value of $X$ closest to the root, multiplied by $1{,}000$ and truncated toward zero.