题目背景

题目描述

小 D 和小 H 有一个长度为 $n$ 的数列 $\{a_1,a_2,\cdots a_n\}$（$a_i\in\{0,1\}$），他们想用一个子数组 $\{a_l,a_{l+1},\cdots a_r\}$ 进行游戏。

对于一个在子数组 $\{a_l,a_{l+1},\cdots a_r\}$ 上进行的游戏，过程如下：小 D 先手，两人会依次对所有 $i$ 满足 $l\le i\le r$，决定是否保留 $a_i$。例如小 D 决定是否保留 $a_l$，小 H 决定是否保留 $a_{l+1}$，小 D 决定是否保留 $a_{l+2}$，以此类推。最后，两人计算所有保留下来的 $a_i$ 的和，如果为偶数，则小 D 赢，如果为奇数，则小 H 赢。

现在小 D 和小 H 对于数列 $\{a_1,a_2,\cdots a_n\}$ 所有子数组 $\{a_l,a_{l+1},\cdots a_r\}$ （$1\le l\le r\le n$）进行游戏，小 D 有个问题，如果两人足够聪明，自己能赢多少次。

为了不让这个游戏变得枯燥，两人会对这个数列进行 $m$ 次区间反转。具体的，如果对区间 $[l,r]$ 进行反转操作，则对于所有满足 $l\le i\le r$ 的 $i$，如果 $a_i=1$，则将 $a_i$ 改为 $0$，否则如果 $a_i=0$，则将 $a_i$ 改为 $1$。

请你在每次修改后回答小 D 的问题。

输入格式

第一行输入两个正整数 $n,m$ 表示数列长度和修改次数。

第二行输入 $n$ 个只包含 $0,1$ 的整数表示 $a_1,a_2,\cdots a_n$。

接下来 $m$ 行，每行输入两个整数 $l,r$，表示对区间 $[l,r]$ 做一次反转操作。

输出格式

输出共 $m$ 行，对每次修改后单独输出一行一个整数表示小 D 问题的答案。

5 4
0 1 1 0 1
1 4
2 3
1 5
2 4

11
9
15
9

提示

【数据范围】

• $1\le n,m\le 2\times 10^5$。
• $1\le l\le r\le n$。
• $a_i\in\{0,1\}$（$1\le i\le n$）。