If we have \(c_i\) people wearing Color \(i\), obviously we can form \(\lfloor\frac{c_i}{2}\rfloor\) pairs wearing the same color. We can move both borders to the left and to the right, maintaining the value of \(\sum\limits_{i=1}^n\lfloor\frac{c_i}{2}\rfloor\) in \(\mathcal O(1)\). Then we can solve it using Mo’s algorithm in \(\mathcal O(N\sqrt{Q})\).

Submission: 29874636.