给定一个长为 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]。