背景

题目描述

给定序列 $a_1,\dots,a_n$ ，$m$ 次询问，每次询问给出 $l,r$ ，问有多少组 $(i,j,k)$ 满足 $l\le i<j<k\le r,\;a_i=a_k>a_j$ 。

输入格式

第一行两个整数 $n,m$。

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

接下来 $m$ 行每行两个整数 $l,r$ 表示一个询问。

输出格式

共 $m$ 行，每行一个整数，依次表示每个询问的答案。

10 5
9 8 5 4 5 1 5 1 5 8
2 8
4 9
7 9
6 7
2 3

4
4
1
0
0

提示

Idea：ccz181078，Solution：ccz181078，Code：ccz181078，Data：ccz181078

所有数值为整数。

对于 $100\%$ 的数据，满足 $1\le a_i\le n$，$1\le l\le r\le n$，$n,m\le 5\times 10^5$。