\(N \leq 10^6\) とそこまで大きくないので, 愚直にシミュレートしても間に合う.