Count Increasing Triplets in Permutation

Given a permutation \(a\) of \(1 \dots n\) and \(q\) queries, each query provides an interval \([l, 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_j < a_k\). This problem asks you to efficiently answer multiple queries based on the given permutation.

inputFormat

The first line contains two integers \(n\) and \(q\), representing the number of elements in the permutation and the number of queries, respectively.

The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\), which form a permutation of \(1 \dots n\).

Each of the next \(q\) lines contains two integers \(l\) and \(r\) describing a query interval.

outputFormat

For each query, output a single line containing the count of triplets \((i,j,k)\) satisfying \(l \le i < j < k \le r\) and \(a_i < a_j < a_k\).

sample

5 2
1 2 3 4 5
1 5
2 4

10
1