Farmer John 认为自己在算法设计上取得重大突破：他声称找到了 3SUM 问题的近线性时间算法。该问题以尚无已知算法能显著优于平方时间而著名。一种表述是：给定整数数组 $s_1,\dots,s_m$，统计互不相同下标 $i,j,k$ 的无序三元组数，使 $s_i+s_j+s_k=0$。

Bessie 为检验此说法，给出含 $N$ 个整数的数组 $A$（$1\leq N\leq5000$）和 $Q$ 个查询（$1\leq Q\leq10^5$），每个有两个下标 $1\leq a_i\leq b_i\leq N$。FJ 必须对每个子数组 $A[a_i\dots b_i]$ 解 3SUM。

不幸他刚发现算法有漏洞。他相信能修复，但在此期间请你帮他通过 Bessie 的测试！

输入格式

第一行空格分隔的整数 $N,Q$。第二行空格分隔的数组元素 $A_1,\dots,A_N$。随后 $Q$ 行各为空格分隔的整数 $a_i,b_i$，表示查询。

保证每个 $A_i$ 满足 $-10^6\leq A_i\leq10^6$。

输出格式

输出 $Q$ 行，第 $i$ 行一个整数，为第 $i$ 个查询的答案。请使用 64 位整数避免溢出。

样例

输入格式 1

7 3
2 0 -1 1 -2 3 3
1 5
2 4
1 7

输出格式 1

2
1
4

说明

第一个查询的三元组为 $(A_1,A_2,A_5)$ 和 $(A_2,A_3,A_4)$。

子任务

• 测试点 2–4：$N\le500$。
• 测试点 5–7：$N\le2000$。
• 测试点 8–15 无额外限制。

题目作者：Dhruv Rohatgi