A sequence $(a_n{)}_{n\ge 0}$ starts with $a_0=3$ and for each $n\ge 0$,

• if $a_n$ is a triangle numberA triangle number is a number of the form $m(m+1)/2$ for some integer $m$., then $a_{n+1}=a_n+1$;
• otherwise, $a_{n+1}=2a_n-a_{n-1}+1$.

The sequence begins: $$3,4,6,7,9,12,16,21,22,24,27,31,36,37,39,42,\dots$$ where triangle numbers are marked red.

The $10$th triangle number in the sequence is $a_{2964}=1439056$.
Find the index $n$ such that $a_n$ is the $70$th triangle number in the sequence.