AT_arc085_d [ARC085F] NRE

[problemUrl]: https://atcoder.jp/contests/arc085/tasks/arc085_d 全ての要素が $ 0 $ の数列 $ a\ =\ \{a_1,\ ...,\ a_N\} $ と，$ 0 $ と $ 1 $ からなる数列 $ b\ =\ \{b_1,\ ...,\ b_N\} $ が与えられます。 どちらも長さは $ N $ です。 あなたは $ Q $ 種類の操作を行うことが可能です。$ i $ 種類目の操作は以下のような動作です。 - $ a_{l_i},\ a_{l_i\ +\ 1},\ ...,\ a_{r_i} $ を全て $ 1 $ に書き換える $ Q $ 種類の操作のうちいくつかを行い，$ a $ と $ b $ のハミング距離， つまり $ a_i\ \neq\ b_i $ なる $ i $ の数を最小化してください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ b_1 $ $ b_2 $ $ ... $ $ b_N $ $ Q $ $ l_1 $ $ r_1 $ $ l_2 $ $ r_2 $ $ : $ $ l_Q $ $ r_Q $

ハミング距離の最小値を出力してください。

### 制約 - $ 1\ \leq\ N\ \leq\ 200,000 $ - $ b $ は $ 0,\ 1 $ からなる - $ 1\ \leq\ Q\ \leq\ 200,000 $ - $ 1\ \leq\ l_i\ \leq\ r_i\ \leq\ N $ - $ i\ \neq\ j $ ならば $ l_i\ \neq\ l_j $ または $ r_i\ \neq\ r_j $ ### Sample Explanation 1 操作を行うと $ a\ =\ \{1,\ 1,\ 1\} $ になり，ハミング距離は $ 1 $ となります。 ### Sample Explanation 2 両方の操作を行うと $ a\ =\ \{1,\ 0,\ 1\} $ になり，ハミング距離は $ 0 $ となります。 ### Sample Explanation 4 何も操作を行わないのが最適な時もあります。