给定一个长为 $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']$ 中的众数。
输入格式
输入的第一行包含两个数 $n$，$m$。
之后一行 $n$ 个数表示这个序列。
之后 $m$ 行，每行两个数 $l$，$r$ 表示一次询问。
输出格式
输出共 $m$ 行，表示每个询问对应的答案。
样例数据
样例 1 输入
10 10 2 2 2 1 2 7 7 9 6 10 1 4 4 4 1 3 2 6 6 6 7 10 2 6 4 10 3 5 3 7
样例 1 输出
2 0 2 1 0 3 1 6 0 1
子任务
Idea：yummy&nzhtl1477，Solution：nzhtl1477，Code：nzhtl1477&czr，Data：nzhtl1477(partially uploaded)
对于 $100\%$ 的数据，其中 $1\le n,m\le 5\times 10^5$，$1\le l\le r\le n$，$1\le a_i\le n$，所有数值为整数。
样例解释：
$[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]$。