Segment

Alice know how to solve the puzzle called counting game.

You are given an array $a$ of $n$ integers numbered from $1$ to $n$ .

You have to perform $q$ queries.

For each query, you are given $m_i$ subsegments. Suppose the left and the right endpoints of the $i$ -th segment are $l_i$ and $r_i$ ( $[l_j,r_j],\;1\le j\le m_i$ ) respectively. You need to calculate the total number of pairs of integers $(p,q)$ , that $p<q \land a_p<a_q \land (\exists 1\le u<v\le m_i,l_u\le p\le r_u,\;l_v\le q\le r_v)$ .

The first line contains two integer $n,q$ ( $1\le n,q\le 3\times 10^5$ ), denoting the length of the array $a$ and the number of queries.

The second line contains $n$ integers $a_1,a_2,\cdots,a_n$ ( $1 \le a_i \le n$ ).

Each of the following blocks of lines contains the description of one query.
For each query, the first line contains an integer $m_i$ , denotes the number of segments. The following $m_i$ lines contains two integers $l_i, r_i$ ( $1 \le l_i < r_i \le n$ ), representing the $m_i$ segments in the query.

It guaranteed that $1\le \sum\limits_{i=1}^m m_i\le 3\times 10^5$ , $m_i\ge 1$ .

详情