$2$-adic order bound for $P(x)$ 
Let $P(x) \in \mathbb{Z}[x]$ be a monic polynomial of degree $n$, with no integer roots, such that $\upsilon_2(P(m))$ can assume $n$ different positive values, where $m \in \mathbb{Z}$ and $\upsilon_2(P(m))$ is the $2$-adic order of $P(m)$. Hence $\upsilon_2(P(m)) < \dfrac{3n^2}{2}$ for all integer $m$.

This problem was proposed at a Korean math program for undergraduates.
How this bound $\dfrac{3n^2}{2}$ can be obtained?
Can this problem be generalized, i.e., if the $p$-adic valuation of $P(x)$ can assume $k$ different positive values on integer arguments what bounds are known for $\upsilon_p(P(m))$?
 A: Let $P$ be a monic polynomial of degree $n$ over $\mathbb Z$. Let $\alpha_1,\dots, \alpha_n$ be its roots, which we view as elements of $\overline{\mathbb Q_p}$. Then all $p$-adic valuations of $P$ are at most
$$ n \left( k -1 + \frac{p}{(p-1)^2}\right)$$
and this is close to sharp.

Proof: Let $m$ be a value on which it attains a large $p$-adic valuation.
For each nonnegative integer $t$, let $$v_t = \sum_{i=1}^n  \min(  v_p( \alpha_i -m), t)$$
Then $v_t$ is a strictly increasing sequence until it reaches its maximum value of $\sum_{i=1}^n v_p(\alpha_i-m) = v_p(P(m))$. We have $v_0=0$ so $$v_p(P(m)) = \sum_{t=0}^{\infty} ( v_{t+1} - v_t).$$
For each value of $t$ before the maximum, there are two possibilities. Either some value in $[v_t, v_{t+1})$ occurs as $v_p ( P (x))$ for some $x \in \mathbb Z$ or not.
Because none of these intervals contains the maximum, there are at most $k-1$ values of $t$ of the first type. For each one, $v_{t+1} - v_t \leq n$, so these values contribute at most $n(k-1)$ to the sum.
Now let's fix one $t$ of the second type. For any integer $u$ that's congruent to $1$ mod $p$, we have $$v_p ( P (m + p^t u ))  =\sum_{i=1}^n v_p ( \alpha_i - m - p^t u ) \geq \sum_{i=1}^n \min ( v_p ( \alpha_i - m ), t) = v_t$$ so $v_p ( P (m+p^t u ) ) \geq v_{t+1}$ by assumption. Thus
$$ v_{t+1} - v_t \leq v_p (  P ( m + p^t u)) - v_t = \sum_{i=1}^n ( v_p ( \alpha_i - m - p^t u )  - \min ( v_p ( \alpha_i - m ), t))$$
The difference $ v_p ( \alpha_i - m - p^t u )  - \min ( v_p ( \alpha_i - m ) $ vanishes unless $v_p ( \alpha_i -m ) =t$ , in which case it is $v_p (  \frac{\alpha_i -m}{p^t} - u ) $. So
$$ v_{t+1} - v_t \leq \sum_{ i \mid v_p (\alpha_i -m)=t} v_p \left(  \frac{\alpha_i -m}{p^t} - u \right)$$
This inequality, because it holds for all integers nonzero mod $p$, holds for all $p$-adic numbers nonzero mod $p$. Integrate it over all $p$-adic numbers nonzero mod $p$ (or sum over numbers nonzero mod $p$ in a large interval, divide by the length of the interval, and take the limit.
$$ \frac{p-1}{p} (v_{t+1} - v_t) \leq \sum_{ i \mid v_p (\alpha_i -m)=t}  \int_{ u \in \mathbb Z_p^\times} v_p \left(  \frac{\alpha_i -m}{p^t} - u \right) du \leq \sum_{ i \mid v_p (\alpha_i -m)=t}  \left( \frac{1}{p} + \frac{1}{p^2} + \dots \right) = \sum_{ i \mid v_p (\alpha_i -m)=t}  \frac{1}{p-1} $$
because the function $v_p (  \frac{\alpha_i -m}{p^t} - u )$ is at most $1$ restricted to $u$ that are congruent to $\frac{\alpha_i -m}{p^t}$ mod $p$ plus $1$ restricted to $u$ that are congruent to $\frac{\alpha_i -m}{p^t}$ mod $p^2$ plus...
Thus
$$v_{t+1} - v_t= \left| \{ i \mid v_p (\alpha_i -m)=t\}\right| \frac{p} {(p-1)^2} $$
Summing this over all $t$, these terms contribute at most $  n \frac{p}{ (p-1)^2}$ since we can have $ v_p (\alpha_i -m)=t$ for at most one $t$. Adding the contribution of the two types of terms, we get the claim.

Construction:
Let $n = 2 \cdot p^r$ for $r>0$.
Take $$P(m) = \prod_{i=0}^{p^{r}-1} (m - p^{k-1} (i + p^{r-1} \sqrt{p})) (m- p^{k-1} (i-p^{r-1} \sqrt{p})) = \prod_{i=0}^{p^{r}-1} ( (m-p^{k-1} i)^2 -p^{2k+2r-3} )$$
which indeed is monic with integer coefficients.
Then $v_p(P(m))$ takes the value $2 p^r  v_p(P (m))$ if $v_p(P(m)) < k-1$. So to show it takes at most $k$ values, it suffices to show it takes the same value at all $m$ with $v_p(m) \geq k-1$. For such $m$, we must have $m$ congruent to $j p^{k-1} \mod p^{ r+ k-1}$ for some $0 \leq j < p^{r}$.
Then
$$v _p ( m-  p^{k-1} ( i \pm p^{r-1} \sqrt{p} ))  = v_p (  p^{k-1} ( j-i \pm p^{r-1} \sqrt{p} + O ( p^r)))$$
which if $j-i$ has $p$-adic valuation $r$, is $k-1 + v_p(j-i)$ because the $j-i$ term dominates, and if $j-1$ has $p$-adic valuation $r-1$, is $ k-1 + r - \frac{1}{2}$ because the $p^{r-1} \sqrt{p}$ term dominates.
For any $j$, we have $v_p(j-i)=0$ for $p^r - p^{r-1}$ values of $i$, $=1$ for $p^{r-1} - p^{r-2}$ values of $i$, and so on, up to $p$-adic valuation at least $r$ for one value of $i$.
Summing over all $i$, we get $$ \sum_{i=0}^{p^r-1} \left(k-1 + \min \left( v_p (j-i), r-\frac{1}{2} \right) \right) =p^r (k-1) +  p^{r-1} + p^{r-2} + \dots + 1 - \frac{1}{2},$$ and doubling to account for signs gives $$v_p ( P(m)) =  2 p^r (k-1) + \frac{2(p^r -1)}{p-1} -1 = n \left( k-1 + \frac{1}{p-1} \right) - O(1),$$ which almost matches our upper bound.
