剪接

• 时间限制：$2$ 秒
• 空间限制：$512\ \mathrm{MB}$

题目描述

一条展示纸带由 $n$ 张依次相连的色卡组成。制作时，第 $i$ 张色卡被标上永久的原编号 $i$，颜色编号为 $a_i$。后续即使部分色卡被取下，剩余色卡的原编号也不会重新排列。

为了保证初始展示清晰，任意两张初始相邻色卡的颜色都不同，即对所有 $1\le i<n$，都有 $a_i\ne a_{i+1}$。

展示过程中需要按原编号删去若干段材料。色卡被取下后，它原本左右两侧的剩余部分会直接接合。若接口两侧恰好是两张同色色卡，胶合机会将这一对色卡同时剥离，并在新形成的接口处重复检查。

现在依次进行 $q$ 次剪接。一次剪接给出两个原编号 $l,r$，并严格按照下列顺序处理：

1. 取下当前仍在纸带上、且原编号属于 $[l,r]$ 的全部色卡；这些色卡可能一张都不剩，若存在则在当前纸带上构成一个连续段；
2. 如果确实取下了至少一张色卡，就将剩余纸带按原顺序重新接好；
3. 若新接口两侧的两张色卡颜色相同，则将这两张色卡同时取下，再检查由此产生的新接口；
4. 重复上一步，直到接口到达纸带一端，或接口两侧颜色不同。

级联剥离只从本次删除后形成的接口向外扩展。已经取下的色卡永久消失。若一次剪接开始时，所有原编号属于 $[l,r]$ 的色卡都早已被取下，则本次不会形成新接口，也不会触发额外剥离。

请在每次剪接后，输出纸带上剩余的色卡数量。

输入格式

第一行两个正整数 $n,q$，分别表示色卡数量和剪接次数。

第二行 $n$ 个正整数 $a_1,a_2,\ldots,a_n$，表示每张色卡的颜色。

接下来 $q$ 行，第 $i$ 行两个正整数 $l_i,r_i$，表示第 $i$ 次剪接给出的原编号区间。

输出格式

输出 $q$ 行，第 $i$ 行一个非负整数，表示第 $i$ 次剪接后剩余的色卡数量。

输入样例 1

7 3
1 2 3 2 1 4 5
3 3
6 6
1 7

输出样例 1

2
1
0

输入样例 2

8 4
1 2 3 4 5 3 2 6
4 5
2 7
1 1
8 8

输出样例 2

2
2
1
0

输入样例 3

见附件 sample/splice3.in

输出样例 3

见附件 sample/splice3.out

样例说明

样例 $1$ 的第一次剪接中，原编号为 $3$ 的色卡被取下。随后颜色为 $2$ 的两张色卡在接口处相遇并被取下，颜色为 $1$ 的两张色卡也随之相遇并被取下，最后只剩下原编号为 $6,7$ 的两张色卡。

样例 $2$ 的第一次剪接后，颜色为 $3$ 的两张色卡先被取下，接着颜色为 $2$ 的两张色卡被取下，最后剩余原编号为 $1,8$ 的两张色卡。第二次剪接给出的区间中已经没有色卡，因此纸带不发生变化。

数据范围

对于所有测试点，$1\le n,q\le 5\times 10^5$，$1\le a_i\le 10^9$，$1\le l_i\le r_i\le n$。

数据保证对所有 $1\le i<n$，均有 $a_i\ne a_{i+1}$。