Triplet Query

Given a sequence \(a_1, \dots, a_n\) and \(m\) queries, each query provides two integers \(l\) and \(r\). For each query, count the number of triplets \((i,j,k)\) such that \(l \le i < j < k \le r\) and

\[ a_i = a_k > a_j \]

This means that the first and the third elements in the triplet have the same value and are strictly greater than the middle element.

inputFormat

The first line contains two integers \(n\) and \(m\) --- the length of the sequence and the number of queries.

The next line contains \(n\) integers \(a_1, a_2, \dots, a_n\), representing the sequence.

Each of the following \(m\) lines contains two integers \(l\) and \(r\), representing a query.

outputFormat

For each query, output a single line with the number of triplets satisfying \(a_i = a_k > a_j\) for indices \(i, j, k\) such that \(l \leq i < j < k \leq r\).

sample

5 3
1 2 1 2 2
1 5
2 4
3 5

2
1
0