该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

【题目描述】

小灰灰最近特别喜欢研究那些很长很简单的序列，他有一个仅由数字 $\{1,2,3\}$ 构成的长度为 $n$ 的序列，第 $i$ 个元素是 $a_i$。

小灰灰准备了 $q$ 次询问，每次给出一个区间 $[l,r]$。对于每次询问，你需要求出片段 $a_l,a_{l+1},\ldots,a_r$ 中逆序对的个数。

如果在这个片段中，存在一对位置满足前面的元素比后面的元素数值大，那么它们就构成一对逆序对。

• 形式化地说，对于一次询问 $[l,r]$，若存在一对有序对 $(i,j)$，满足 $l\le i<j\le r$ 且 $a_i>a_j$，那么这个有序对就是该询问区间内的一对逆序对。

你需要依次回答所有询问。

【输入描述】

第一行输入两个整数 $n,q$。

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

接下来 $q$ 行，每行输入两个整数 $l,r$，表示一次询问。

保证：

• $1\le n,q\le 2\times 10^5$；
• $a_i\in\{1,2,3\}$；
• $1\le l\le r\le n$。

【输出描述】

输出 $q$ 行，每行一个整数。

第 $k$ 行表示第 $k$ 次询问区间内的逆序对个数。

【样例 1】

【样例 1 输入】

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

【样例 1 输出】

2
2
5
0

【样例 1 解释】

第一次询问的片段为 $3,1,2$。

其中 $(1,2)$ 满足 $a_1=3>a_2=1$，构成一对逆序对。

$(1,3)$ 满足 $a_1=3>a_3=2$，也构成一对逆序对。

除此之外没有其它逆序对，所以答案为 $2$。

第四次询问只有一个元素，不存在满足 $i<j$ 的位置对，所以答案为 $0$。

【样例 2】

【样例 2 输入】

10 5
2 3 1 2 1 3 2 1 3 1
1 10
1 3
4 8
2 6
8 10

【样例 2 输出】

19
2
5
4
1

【样例 2 解释】

对于第一次询问，统计整个序列中所有满足前面的数大于后面的数的位置对，一共有 $19$ 对。

【样例 3】

见选手目录下的 Data/sample3.in 和 Data/sample3.ans。

该样例满足 $n,q\le 1000$。

【样例 4】

见选手目录下的 Data/sample4.in 和 Data/sample4.ans。

该样例满足 $a_i\in\{1,2\}$。

【样例 5】

见选手目录下的 Data/sample5.in 和 Data/sample5.ans。

该样例仅满足完整数据范围，无额外限制。

【数据规模与约定】

对于 $100\%$ 的数据，满足 $1\le n,q\le 2\times 10^5$，$a_i\in\{1,2,3\}$，$1\le l\le r\le n$。

点击下载本题选手目录