2つの要素の積が平方数になる条件は, 2つの数を素因数分解したときに乗数が奇数の素因数が一致することである. (-1 も含む)

よって, すべての要素を素因数分解して乗数が奇数になる素因数だけ掛けたものに変換する.

あとは連続する部分列を列挙してそれぞれの部分列において異なる素因数積の数を数えればいい. ただし, 0 はワイルドカードの扱いで, どの素因数積にも組み込める.

ただし, 時間制限が厳しいので, 異なる素因数積の数を数えるのに連想配列を使うと間に合わなかった. 素因数積は同じかどうかだけわかればいいので, 座標圧縮して配列で管理すれば間に合った.