Let \(M\) be the maximum value in the sequence \(A\).

Pairs that are not good are called “bad pairs.”

Let’s consider the conditions for a bad pair. In fact, by using the pigeonhole principle, one can see that the following holds for bad pairs:

• The length of a bad pair is at most \(2M\).

This is because if the length is \(2M+1\) or more, some integer will be contained three or more times, trivially forming an arithmetic sequence.

From this fact, for each \(l\), we only need to check whether \((l,l),(l,l+1),\ldots,(l,\min(l+2M,N))\) are bad intervals.

This can be done in \(\mathrm{O}(NM^2)\) overall by appropriately managing the set of integers currently contained in the sequence and the set of integers that, if included next in the sequence, would result in a good pair.

The constraints also allow for \(\mathrm{O}(NM^3)\) solutions or \(\mathrm{O}(NM^4)\) solutions with a good constant factor to pass.