给定 $n$ 个整数 $a_1, a_2, \cdots, a_n$。有 $q$ 次询问，每次询问 $a[l\cdots r]$ 的逆序对数。
输入格式
输入的第一行包含两个整数 $n$ 与 $q$。
接下来一行，包含 $n$ 个整数 $a_1, a_2, \cdots, a_n$。
输出格式
对于每组询问，输出一行一个整数，表示答案。
样例数据
样例输入
7 6
10 25 3 6 17 24 1
2 5
1 4
1 6
3 5
4 7
1 7样例输出
3
4
6
0
3
12子任务
对于所有数据，$1 \leq n,q \leq 3 \times 10^5, 0 \leq a_i \leq 10^9$。
- 子任务 1（10 分）：$n,q \leq 1000$。
- 子任务 2（20 分）：$n,q \leq 5\times 10^4$。
- 子任务 3（20 分）：$n,q \leq 10^5$。
- 子任务 4（20 分）：$n,q \leq 2 \times 10^5$。
- 子任务 5（30 分）：没有额外的限制。