给定一个长为 $n$ 的序列 $a$，定义 $x$ 为区间 $[l,r]$ 的众数当且仅当不存在 $y$ 使得 $y$ 在区间 $[l,r]$ 中的出现次数大于 $x$ 在区间 $[l,r]$ 中的出现次数。

有 $m$ 次询问，每次询问给出 $l$，$r$，求有多少二元组 $(l',r')$ 满足 $l \le l' \le r' \le r$ ，且 $[l',r']$ 的区间长度为奇数，且 $(l'+r')/2$ （注意这里是下标而不是下标对应的值）是区间 $[l',r']$ 中的众数。

传题人注：SCNUOJ 仅测试 THU 原数据的 #1, #2, #11, #12, #21, #22，如果你在此处得到了 AC，可前往 THUSAAC 获取完整数据进行进一步测试。

输入的第一行包含两个数 $n$，$m$。

之后一行 $n$ 个数表示这个序列。

之后 $m$ 行，每行两个数 $l$，$r$ 表示一次询问。

其中 $1\le n\le 5\times 10^5，1\le m\le 10^6$，$1\le l\le r\le n$，$1\le a_i\le n$，所有数值为整数。

输出共 $m$ 行，表示每个询问对应的答案。

$[1,4]$ 中满足条件的子区间为 $[1,3]$，$[2,2]$。

$[1,3]$ 中满足条件的子区间为 $[1,3]$，$[2,2]$。

$[2,6]$ 中满足条件的子区间为 $[2,2]$。

$[7,10]$ 中满足条件的子区间为 $[7,7]$，$[8,10]$，$[10,10]$。

$[4,10]$ 中满足条件的子区间为 $[7,7]$，$[6,8]$，$[5,9]$，$[4,10]$，$[8,10]$，$[10,10]$。

$[3,7]$ 中满足条件的子区间为 $[7,7]$。