P7139 [THUPC 2021 初赛] 区间众数

## 注意： 本题不提供评测，需要提交本题请到 [[Ynoi2008]rsmemq](/problem/P7125)。

给定一个长为 $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$ 表示一次询问。 其中 $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】** $[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]$。 **【题目来源】** 来自 2021 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2021）初赛。 题解等资源可在 查看。