Background

Problem Description

Given a sequence $a_1,\dots,a_n$ and $m$ queries. Each query gives $l,r$. For each query, find how many triples $(i,j,k)$ satisfy $l\le i<j<k\le r$ and $a_i=a_k>a_j$.

Input Format

The first line contains two integers $n,m$.

The second line contains $n$ integers $a_1,\dots,a_n$.

The next $m$ lines each contain two integers $l,r$, representing a query.

Output Format

Output $m$ lines. Each line contains one integer, the answer to each query in order.

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

Hint

Idea: ccz181078, Solution: ccz181078, Code: ccz181078, Data: ccz181078.

All values are integers.

For $100\%$ of the testdata, $1\le a_i\le n$, $1\le l\le r\le n$, and $n,m\le 5\times 10^5$.

Translated by ChatGPT 5