Counting Increasing Pairs in Segmented Queries

You are given a permutation \(a_1, a_2, \dots, a_n\) of \(n\) distinct integers and \(m\) queries. In each query, you are given \(m_i\) disjoint intervals \([l_j, r_j]\) (with \(1 \le l_j \le r_j \le n\) and \(r_j < l_{j+1}\) for \(1 \le j < m_i\)). For the current query, count the number of ordered pairs \((p,q)\) such that:

• \(p < q\) and \(a_p < a_q\), and
• There exist indices \(u, v\) with \(1 \le u < v \le m_i\) such that \(p \in [l_u,r_u]\) and \(q \in [l_v,r_v]\).

Note: Since the intervals in a query are given in increasing order and are pairwise disjoint (i.e. \(r_j < l_{j+1}\)), any index in an earlier interval is guaranteed to be less than any index from a later interval. The challenge is to count only those pairs \((p,q)\) where \(a_p < a_q\).

Hint: Process the segments in order. For each segment, count for each element how many elements in all previously processed segments are smaller, and then update your data structure accordingly. A Binary Indexed Tree (Fenwick Tree) can be used to achieve this efficiently.

inputFormat

The input is given in the following format:

 n m
 a1 a2 ... an
For each of the m queries:
mi
l1 r1
l2 r2
...
lmi rmi

It is guaranteed that the given array is a permutation of \(n\) distinct integers, and for each query, the intervals satisfy \(1 \leq l_j \leq r_j \leq n\) and \(r_j < l_{j+1}\) for all valid \(j\).

outputFormat

For each query, output a single integer on a new line representing the number of pairs \((p,q)\) that satisfy the conditions.

sample

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

6
0