Migrated from Lutece 2540 区间逆序对

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

数列 $a$ 的一组逆序对是指一对位置 $(i,j)$ 满足 $i<j$ 但 $a_i>a_j$。例如 $a=\{3,1,2\}$ 的逆序对数量为 $2$，满足条件的 $(i,j)$ 分别是 $(1,2),(1,3)$。

一个数列 $a$ 的子区间 $[l,r]$ 是指数列 $\{a_l,a_{l+1},\ldots ,a_{r-1},a_{r}\}$。

现在给定一个数列 $a$，请求出他的多个子区间的逆序对数量。

Input

第一行两个正整数 $n,m$，分别表示数列长度和子区间个数。

第二行 $n$ 个正整数，第 $i$ 个数表示 $a_i$。

接下来 $m$ 行，每行两个正整数 $l,r$ 表示一个子区间 $[l,r]$。

Output

$m$ 行，每行一个正整数，表示子区间的逆序对数量。

Samples

3 2
3 1 2
1 2
1 3

1
2

Constraints

$1 \leq n,m \leq 2\times 10^5,1\le a_i\le n,1\le l\le r\le n$

Note

请注意 $a$ 并不保证是一个排列。

Resources

2021 UESTC ICPC Training for Data Structures