题目描述

小林把 $n$ 个数字从左到右写成一排，第 $i$ 个数字为 $a_i$。

对于一个区间 $[l,r]$，若 $l\le i<r$ 且 $a_i=a_{i+1}$，就称位置 $i$ 和 $i+1$ 构成一对相邻相等对。不同的相邻位置分别计数，即使它们共用一个位置。

现在有 $q$ 次询问，每次给出 $l,r$，请计算完全位于该区间内的相邻相等对数量。数组始终不变。

输入格式

第一行两个整数 $n,q$。

第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

接下来 $q$ 行，每行两个整数 $l,r$，表示一次询问。

输出格式

输出 $q$ 行，每行一个整数，表示对应询问的答案。

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

3
2
0
1

1 1
1000000000
1 1

0

样例 1 解释

第一问包含 $(1,2)$、$(3,4)$、$(4,5)$ 三对。第二问包含 $(3,4)$、$(4,5)$ 两对。只有一个位置的区间不包含相邻对。

样例 2 解释

区间只有一个位置，答案为 $0$。

数据范围与提示

对于所有测试点：$1\le n,q\le 200000$，$0\le a_i\le 10^9$，$1\le l\le r\le n$。

共 $20$ 个测试点，每个测试点 $5$ 分，独立计分。以下限制均在完整数据范围的基础上额外成立；未列出的参数仍遵守完整数据范围。

测试点编号	额外规模限制
1—5	$n,q\le30$
6—10	$n,q\le2000$
11—20	无额外限制

时间限制：2 秒。内存限制：128 MiB。