给定 $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 分）：没有额外的限制。