What is the smallest polynomial with almost linear condition?

Question

What is the smallest degree univariate polynomial with $f(0)=0$, $f(1)\in(0,0.5)$ and $f(x)={x-1}+\epsilon$ where $\epsilon\in(-0.5,0.5)$ at every $x\in\{2,\dots,a-1,a\}$?

Can we have $O((\log a)^c)$ degree.