Consider the sequence $1,\underbrace{0,0,...,0}_{n-1}$ gives us $\Big\lfloor \frac{n-1}{2}\Big\rfloor$ such triples. For the proof, induction on $n\in \mathbb{Z}^+$.

We claim that the answer is $\boxed{\left \lfloor \frac{n-1}{2}\right \rfloor}$. For construction, take $1,2,...,n-1,2333333n+66666$. We induct on $n$ to prove the lower bound. When $n$ is even, having the statement for $n-1$ suffices. Now consider the case where $n$ is odd. Consider the sequence obtained by removing $a_1, a_2$ from $\{a_i\}$. If this is an AP then we are done by directly calling out enough non-AP triples. Now suppose it is not. Then by IH there are $\ge \frac{n-3}{2}$ triples within this subsequence, so no triple containing $a_1$ or $a_2$ is bad. $(a_1, a_2, a_3) \implies a_3 - a_2 = a_2 - a_1$, then $(a_2, a_3, a_4), (a_1,a_3,a_5), (a_2,a_4,a_6), (a_1,a_4,a_7),(a_2,a_5,a_8),(a_1,a_5,a_9),...$ will give $a_4, a_5,...$ part of the progression as well, which eventually results in $\{a_i\}$ being an AP entirely, conntradiction.