SE-SKOLORNAS 2013 Problem 5

Let $n \geq 2$ be a positive integer. Show that there are exactly $2^{n-3}n(n-1)$ $n$ -tuples of integers $(a_1,a_2,\dots,a_n)$ , which satisfy the conditions: (i) $a_1=0$ ; (ii) for each $m$ , $2 \leq m \leq n$ , there is an index in $m$ , $1 \leq i_m <m$ , such that $\left|a_{i_m}-a_m\right|\leq 1$ ; (iii) the $n$ -tuple $(a_1,a_2,\dots,a_n)$ contains exactly $n-1$ different numbers.