数列 \(A\) の最大値を \(M\) とします．

良い組でない組を以下では悪い組と呼びます．

悪い組の条件を考えましょう．実は，鳩ノ巣原理を用いることで悪い組について以下が成り立ちます．

• 悪い組の長さは \(2M\) 以下である．

何故ならば，長さが \(2M+1\) 以上のときある整数が \(3\) 個以上含まれ，これらは明らかに等差数列をなすからです．

このことから，各 \(l\) について， \((l,l),(l,l+1),\ldots,(l,\min(l+2M,N))\) が悪い区間かを調べればよいです．

これは（現在数列に含まれている整数の集合、次にこの数字が含まれると良い組となるような整数の集合）を適切に管理することで，全体で \(\mathrm{O}(NM^2)\) で可能です．

なお本制約では，\(\mathrm{O}(NM^3)\) 解法や定数倍の良い \(\mathrm{O}(NM^4)\) 解法でも AC が得られます．