Background

Problem Description

Given a permutation $a_1,\dots,a_n$, there are $m$ queries. In the $i$-th query, you are given $m_i$ intervals $[l_j,r_j],\;1\le j\le m_i$, satisfying $1\le l_j\le r_j\le n,\;r_j<l_{j+1}$. You need to find how many pairs $(p,q)$ satisfy $p<q,\;a_p<a_q$, and there exist $1\le u<v\le m_i$ such that $l_u\le p\le r_u,\;l_v\le q\le r_v$.

Input Format

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

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

Then, for each query, the first line contains $m_i$, followed by $m_i$ lines each containing $l_j,r_j$.

Output Format

Output $m$ lines. The $i$-th line should be the answer to the $i$-th query.

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

1
0

Hint

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

Constraints: For $100\%$ of the testdata, $1\le n\le 5\times 10^5$, $1\le \sum\limits_{i=1}^m m_i\le 5\times 10^5$, $m_i\ge 1$, $1\le a_i\le n$, and all values are integers.

For $0\%$ of the testdata, $n\le 10^3,\;\sum\limits_{i=1}^m m_i\le 10^3$.

For another $10\%$ of the testdata, $m_i\le 10$.

For another $10\%$ of the testdata, $m\le 5$.

For the remaining $80\%$ of the testdata, there are no special constraints.

Translated by ChatGPT 5