UOJ Logo Universal Online Judge

UOJ

附件下载 统计

小重有一个长度为 $n$ 的序列 $a_1, \dots, a_n$,小庆对小重的序列颇感好奇,于是进行了 $q$ 次询问。

每次询问时,小庆会选定一个下标区间 $\{l,l+1, \dots, r\}$ ($1\le l\le r\le n$),然后让小重去枚举每一个 $\{l, l+1, \dots, r\}$ 的子集 $S$,数一数有多少个子集 $S$ 满足 \begin{equation} |\{a_i \mid i \in S\}| = |\{a_i \mid i \in \{l,l+1,\dots,r\}\setminus S \}| \end{equation} 即,在 $S$ 里出现的不同元素组成的不可重集合与在区间里 $S$ 外出现的不同元素组成的不可重集合大小一致。

小庆问了太多次问题之后,小重不堪重负,于是请求你的帮助。由于每次询问的答案可能很大,小庆只想知道答案对 $2^{64}$ 取模之后得到的结果。

输入格式

第一行 $2$ 个正整数 $n,q$。

第二行 $n$ 个正整数 $a_1, \dots, a_n$。

接下来 $q$ 行,每行 $2$ 个正整数 $l,r$,表示一组询问。

输出格式

共 $q$ 行 $q$ 个非负整数表示答案。

样例一

input

12 5
1 1 4 5 1 4 6 6 6 6 6 6
4 7
1 4
2 6
1 9
7 12

output

6
4
8
126
62

explaination

在第一个样例的第一次询问中,合法的集合 $S$ 有 $\{4,5\},\{4,6\},\{4,7\},\{5,6\},\{5,7\},\{6,7\}$。

样例二/三/四/五

见样例下载,它们分别对应子任务 2,3,4,5。

限制与约定

对于全部数据,保证 $1\le n\le 3\times 10^5,1\le q\le 10^5,1\le a_i\le n$。

子任务编号 $n\le$ $q\le$ 其他约定 分值
1 $18$ $10$ $20$
2 $10^3$ $100$ $20$
3 $10^5$ $1000$ $20$
4 $3\times10^5$ $10^4$ $20$
5 $3\times10^5$ $10^5$ $20$

时间限制:$2\texttt{s}$

空间限制:$1\texttt{GB}$