First, for each index \(i\) and each value \(x\), calculate the smallest index \(j>i\) so that \(A_j=x\).

Let \(f_i\) be the smallest index \(j\geq i\) such that \((i,j)\) is a good pair, or \(N+1\) if the index doesn’t exist, and \(g_i\) be the smallest index \(k\geq i\) such that there exists an index \(j\) where \(i<j<k\) and \((A_i,A_j,A_k)\) is an arithmetic progression, or \(N+1\) if the index doesn’t exist. Then \(f_i=\min(f_{i+1},g_i)\).

To calculate \(g_i\), just brute force \(A_j\) and use the precalculation.

This solution should take \(O(NM)\) in both time and space.