背景

题目来源：【HT-130-Div.3】核桃 CSP-J 组模拟赛

HexOI 欢迎您。

题目描述

小 Hex 的班上正在开展一项游戏！

班上有 $n$ 个小朋友围成一圈，其中小 Hex 的编号为 $1$。从小 Hex 开始，小朋友们按顺时针被编号为 $1,2,3,\dots,n$。第 $i$ 个小朋友的左边是第 $i-1$ 号小朋友，右边是第 $i+1$ 号小朋友。特别地，第 $n$ 号小朋友的右边是第 $1$ 号小朋友，第 $1$ 号小朋友的左边是第 $n$ 号小朋友。

由于小朋友们都学习了编程，他们只喜欢 $0$ 和 $1$ 两个数字中的恰好一个数字。初始时，第 $i$ 位小朋友最喜欢的数字为 $a_i$。

小朋友们想交朋友。每一位小朋友都想和他左右相邻的两个小朋友交朋友。朋友之间要有相同的喜好，因此两位小朋友会交朋友当且仅当他们喜欢的数字相同。

现在老师会执行 $m$ 次操作，每次操作会改变一些小朋友喜欢的数字。具体地，第 $i$ 次操作会让 $[l_i,r_i]$ 范围内的所有小朋友喜欢的数字取反$^\dag$。每次操作完后，小朋友们会重新建立朋友关系。

小 Hex 想知道，每一次操作过后，班上共有几对好朋友？

$^\dag$：取反，即 $1$ 变成 $0$，$0$ 变成 $1$。

输入格式

输入的第一行包含两个正整数 $n,m$，分别表示班级人数和修改次数。

输入的第二行包含 $n$ 个整数，第 $i$ 个数表示 $a_i$。

输入的第 $i+2\ (1\leq i \leq m)$ 行包含两个正整数 $l_i,r_i$，表示修改的起点和终点。

输出格式

输出的第 $i\ (1\leq i\leq m)$ 行包含一个非负整数，表示在第 $i$ 次修改后班上好朋友的对数。

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

0
2
4
4

11 10
1 1 0 1 1 0 1 0 1 0 0
1 1
1 4
2 5
1 6
1 4
4 11
4 8
1 6
1 11
10 11

3
1
3
5
5
7
7
5
5
7

提示

【样例 1 解释】

初始序列为 $1,0,0,0$。

第 1 次修改：将编号为 $3$ 的小朋友喜欢的数字取反。

• 新序列：$1,0,\red{1},0$。
• 好朋友对：无，答案为 $0$。详细的解释如下：
  • 对于第 $1$ 号和第 $2$ 号小朋友，他们喜欢的数字不同（$1$ 和 $0$），因此他们不是好朋友；
  • 对于第 $2$ 号和第 $3$ 号小朋友，他们喜欢的数字不同（$0$ 和 $1$），因此他们不是好朋友；
  • 对于第 $3$ 号和第 $4$ 号小朋友，他们喜欢的数字不同（$1$ 和 $0$），因此他们不是好朋友；
  • 对于第 $4$ 号和第 $1$ 号小朋友，他们喜欢的数字不同（$0$ 和 $1$），因此他们不是好朋友。

第 2 次修改：将编号为 $1$ 至 $3$ 的小朋友喜欢的数字取反。

• 新序列：$\red{0,1,0},0$。
• 好朋友对：$(3,4),(4,1)$，答案为 $2$。详细的解释如下：
  • 对于第 $1$ 号和第 $2$ 号小朋友，他们喜欢的数字不同（$0$ 和 $1$），因此他们不是好朋友；
  • 对于第 $2$ 号和第 $3$ 号小朋友，他们喜欢的数字不同（$1$ 和 $0$），因此他们不是好朋友；
  • 对于第 $3$ 号和第 $4$ 号小朋友，他们喜欢的数字相同（都为 $0$），因此他们是好朋友；
  • 对于第 $4$ 号和第 $1$ 号小朋友，他们喜欢的数字相同（都为 $0$），因此他们是好朋友。

第 3 次修改：将编号为 $2$ 的小朋友喜欢的数字取反。

• 新序列：$0,\red{0},0,0$。
• 好朋友对：$(1,2),(2,3),(3,4),(4,1)$，答案为 $4$。详细的解释如下：
  • 对于第 $1$ 号和第 $2$ 号小朋友，他们喜欢的数字相同（都为 $0$），因此他们是好朋友；
  • 对于第 $2$ 号和第 $3$ 号小朋友，他们喜欢的数字相同（都为 $0$），因此他们是好朋友；
  • 对于第 $3$ 号和第 $4$ 号小朋友，他们喜欢的数字相同（都为 $0$），因此他们是好朋友；
  • 对于第 $4$ 号和第 $1$ 号小朋友，他们喜欢的数字相同（都为 $0$），因此他们是好朋友。

第 4 次修改，将编号为 $1$ 至 $4$ 的小朋友喜欢的数字取反。

• 新序列：$\red{1,1,1,1}$。
• 好朋友对：$(1,2),(2,3),(3,4),(4,1)$，答案为 $4$。详细的解释如下：
  • 对于第 $1$ 号和第 $2$ 号小朋友，他们喜欢的数字相同（都为 $1$），因此他们是好朋友；
  • 对于第 $2$ 号和第 $3$ 号小朋友，他们喜欢的数字相同（都为 $1$），因此他们是好朋友；
  • 对于第 $3$ 号和第 $4$ 号小朋友，他们喜欢的数字相同（都为 $1$），因此他们是好朋友；
  • 对于第 $4$ 号和第 $1$ 号小朋友，他们喜欢的数字相同（都为 $1$），因此他们是好朋友。

【样例 3】

见选手目录下的 friends/friends3.in 与 friends/friends3.ans。

该样例满足测试点 $1,2$ 的约束条件。

【样例 4】

见选手目录下的 friends/friends4.in 与 friends/friends4.ans。

该样例满足测试点 $3$ 的约束条件。

【样例 5】

见选手目录下的 friends/friends5.in 与 friends/friends5.ans。

该样例满足测试点 $4$ 的约束条件。

【样例 6】

见选手目录下的 friends/friends6.in 与 friends/friends6.ans。

该样例满足测试点 $5,6$ 的约束条件。

【样例 7】

见选手目录下的 friends/friends7.in 与 friends/friends7.ans。

该样例满足测试点 $7,8$ 的约束条件。

【样例 8】

见选手目录下的 friends/friends8.in 与 friends/friends8.ans。

该样例满足测试点 $9\sim 12$ 的约束条件。

【样例 9】

见选手目录下的 friends/friends9.in 与 friends/friends9.ans。

该样例满足测试点 $13,14$ 的约束条件。

【样例 10】

见选手目录下的 friends/friends10.in 与 friends/friends10.ans。

该样例满足测试点 $15\sim 20$ 的约束条件。

【数据范围】

对于所有测试数据，保证：

• $3\leq n\leq 10^5$；
• $1\leq m\leq 10^5$；
• 对于所有 $i(1\leq i\leq n)$，均有 $a_i=0$ 或 $a_i=1$；
• 对于所有 $i(1\leq i\leq m)$，均有 $1\leq l_i\leq r_i\leq n$。

::cute-table{tuack}

测试点编号	$n$	$m$	$a_i(1\leq i\leq n)$	特殊性质
$1,2$	$\leq 10^5$	$=1$	无
$3$	$\leq 10^3$		^	A
$4$	^			B
$5,6$			$=i\bmod 2$	无
$7,8$			$=0$	^
$9\sim 12$			无
$13,14$	$\leq 10^5$		$=0$
$15\sim 20$	^		无

特殊性质 A：对于所有 $i(1\leq i\leq m)$，都有 $l_i=2$ 且 $r_i=n-1$。

特殊性质 B：对于所有 $i(1\leq i\leq m)$，都有 $l_i=r_i$。