First note that since $(a_i)$ is strictly increasing, and $a_1 \geq 0$, we have that $a_n \geq n - 1$ for all $n$. Note that $a_n = n - 1$ for all $n$ satisfies the conditions of the problem. Now suppose that $a_k \geq k$ for some $k$, and additionally that this is the smallest $k$ for which this occurs, so that $a_i = i - 1$ for $1 \leq i < k$. We note that since $(a_i)$ is increasing, we then have that $a_n \geq n$ for all $n \geq k$. For any $n > k$, we have that $a_n \mid a_{n - 1} + n$. But $a_{n - 1} < a_n$ and $n \leq a_n$, and so we have that $a_{n - 1} + n < 2a_n$, which then implies that $a_{n - 1} + n = a_n$. If $k \neq 1$, this this holds for $n = k$ as well. Thus if $k > 1$, then we have that $a_k = a_{k - 1} + k = 2k - 2$. Now for any $n > k$, it follows that $a_n = a_{n - 1} + n = a_{n - 2} + n + (n - 1) = \dots = a_k + (k + 1) + (k + 2) + \dots + n = a_k + \frac{n(n + 1)}{2} - \frac{k(k + 1)}{2}$. It follows that all possible sequences are given by $a_n = n - 1$ for all $n$. $a_n = \frac{n(n + 1)}{2} + a_1 - 1$ for all $n$ $a_n = n - 1$ if $n < k$, and $a_n = \frac{n(n + 1)}{2} - \frac{k(k + 1)}{2} + 2k - 2$ for $n \geq k$.