障害物の置かれたグリッド上で飛車が2回で移動できる範囲を求める。

問題 長さ $n$ の数列 $A$ と $q$ 個のクエリが与えられる．各クエリにおいて，与えられた区間における $A _ i$ の種類数を答えよ．( $1 \leq n, q \leq 5 \times 10 ^ {5}$, $1 \leq A _ i \leq n$ )