International Mathematical Olympiad 2009 Problem 3

Suppose that $s_1, s_2, s_3, \ldots$ is a strictly increasing sequence of positive integers such that the subsequences

$$s_{s_1}, s_{s_2}, s_{s_3}, \ldots \quad \text{and} \quad s_{s_1 + 1}, s_{s_2 + 1}, s_{s_3 + 1}, \ldots$$

are both arithmetic progressions. Prove that the sequence $s_1, s_2, s_3, \ldots$ is itself an arithmetic progression.