I think I have an idea for the proof: let's call $G_1, G_2, \dots , G_{p+1}$ the sets with $p+1$ consecutive elements and minimal element $-p-1+k$ for $G_k$, $1\le k\le p+1$. Clearly, if a function satisfies the given condition then its image is a subset of at least one of the $G$'s. Denote as $F_i$ the set of function $f: \{ 1,2,...,n\}\to G_i$. We want to find $|F_1\cup \dots\cup F_{p+1}|$. We are going to use the principle of inclusion-exclusion: \[|F_1\cup \dots\cup F_{p+1}|=|F_1|+\dots+|F_{p+1}|-\sum_{i<k}{|F_i\cap F_k|}\dots\] So the first $p+1$ terms on the $RHS$ are going to sum up to $(p+1)^{n+1}$. Let's analyse a general intersection $F_a\cap F_b\dots \cap F_w$ with $a<b<\dots <w$. We note that the cardinality of the intersection depends only on $a$ and $w$. So for a cardinality $p-k$, $1\le k\le p-1$ we find on the $RHS$: $p-k$ subsets of cardinality $p-k$ among the $2$-intersections, $\binom{k}{1} (p-k)$ among the $3$-intersections, $\dots$, $\binom{k}{k} (p-k)$ among the $k$-intersections. All those term cancel because of the well-known result: $\binom{n}{0}-\binom{n}{1}+\binom{n}{2}-\cdots =0$. We are left with $ {{(p+1)}^{n+1}}-{{p}^{n+1}} $

Here is another proof. Let $N_q$ denote the number of such functions, whose maximum value is $q$. We will consider two cases. Case 1: $q \in \{0,1,\dots,p\}$: In this case, the smallest value that the function can take is at least $q-p$. Hence, all entries are confined to the set $S = \{q-p,q-p+1,\dots,q\}$. The number of functions $f: \{0,1,\dots,n\}\to S$ is $(p+1)^{n}$. However, $p^{n}$ of them does not take a maximum of $q$. Hence, $\boxed{N_q = (p+1)^{n}-p^{n}}$ for $q \in \{0,1,\dots,p\}$. Case 2 : $q \in \{-p,-p+1,\dots,-1\}$: This time, for any such $f(\cdot)$, the values are confined to set $\{-p,-p+1,\dots,q\}$. With the same reasoning as above, we conclude that for this case $\boxed{N_q = (q+p+1)^{n}-(q+p)^n}$. Finally, we will count the total number of such functions as follows: \begin{align*} N & = \sum_{q=-p}^p N_q \\ & = \sum_{q=-p}^{-1} [(q+p+1)^{n}-(q+p)^n] + \sum_{q=0}^p [(p+1)^{n}-p^{n}] \\ & = p^n + (p+1)(p+1)^n - (p+1)p^n \\ & = (p+1)^{n+1} - p^{n+1}. \end{align*}$\square$