Given a permutation $a_1, \dots, a_n$, there are $m$ queries. The $i$-th query provides $m_i$ intervals $[l_j, r_j]$ for $1 \le j \le m_i$, satisfying $1 \le l_j \le r_j \le n$ and $r_j < l_{j+1}$. You need to find the number of pairs $(p, q)$ such that $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$ and $l_v \le q \le r_v$.

Input

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

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

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

Output

Output $m$ lines, each containing the answer for the corresponding query.

Constraints

For $100\%$ of the data, $1 \le n \le 5 \times 10^5$, $1 \le \sum_{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 data, $n \le 10^3$ and $\sum_{i=1}^m m_i \le 10^3$.

For an additional $10\%$ of the data, $m_i \le 10$.

For an additional $10\%$ of the data, $m \le 5$.

For the remaining $80\%$ of the data, there are no special restrictions.

Examples

Input 1

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

Output 1

1
0