IMO 2009 Problem 3

Suppose that $s_1, s_2, s_3, \dots$ is a strictly increasing sequence of positive integers such that the subsequences $s_{s_1}, s_{s_2}, s_{s_3}, \dots$ and $s_{s_{1+1}}, s_{s_{2+1}}, s_{s_{3+1}}, \dots$ are both arithmetic progressions. Prove that the sequence $s_1, s_2, s_3, \dots$ is itself an arithmetic progression.