【题目描述】

小灰灰有一个长度为 $n$ 的序列：$a_1, a_2, \dots, a_n$。

这个序列中仅有数字 1、2 和 3，也就是说对于任意的 $a_i$ 均有 $a_i \in \{1, 2, 3\}$。

小蓝对这个序列提出了 $m$ 个询问，第 $i$ 个询问，指定了一个区间 $[l_i, r_i]$，她想知道需要执行下面的操作至少多少次才能把区间中元素从小到大排好序。

• 一次操作是指，选择区间 $[l_i, r_i]$ 的两个不同数字，然后交换这两个数字的位置。

这里的所有询问均独立，也就是说每次小蓝只是提出问题，你做出回答（如果修改，需要至少多少次操作），并没有真的修改 $a$ 序列。

【输入描述】

第一行输入两个整数 $n$ 和 $m$。

接下来一行输入 $n$ 个整数，其中第 $i$ 个整数表示 $a_i$。

接下来 $m$ 行，第 $i$ 行输入两个整数 $l_i$ 和 $r_i$。

保证：

• $1 \le n, m \le 3 \times 10^5$
• $a_i \in \{1, 2, 3\}$
• $1 \le l_i \le r_i \le n$

【输出描述】

输出共 $m$ 行，第 $i$ 行输出将区间 $[l_i, r_i]$ 排序所需的最少交换次数。

【样例 1】

【样例 1 输入】

9 5
2 2 1 3 3 3 2 3 1
1 9
2 7
4 6
1 3
7 9

【样例 1 输出】

4
2
0
1
2

【样例 1 解释】

• 查询 $[1,9]$（对应子数组 2 2 1 3 3 3 2 3 1）：
  1. 交换 $a_1$ 和 $a_3 \rightarrow$ 1 2 2 3 3 3 2 3 1
  2. 交换 $a_2$ 和 $a_9 \rightarrow$ 1 1 2 3 3 3 2 3 2
  3. 交换 $a_4$ 和 $a_7 \rightarrow$ 1 1 2 2 3 3 3 3 2
  4. 交换 $a_5$ 和 $a_9 \rightarrow$ 1 1 2 2 2 3 3 3 3 共 4 次交换。
• 查询 $[2,7]$（对应子数组 2 1 3 3 3 2）：
  1. 交换子数组中的位置 1 和 2（即原序列位置 2 和 3） $\rightarrow$ 1 2 3 3 3 2
  2. 交换子数组中的位置 3 和 6（即原序列位置 4 和 7） $\rightarrow$ 1 2 2 3 3 3 共 2 次交换。
• 查询 $[4,6]$（对应子数组 3 3 3）：已排序，0 次交换。
• 查询 $[1,3]$（对应子数组 2 2 1）：
  1. 交换位置 1 和 3 $\rightarrow$ 1 2 2 共 1 次交换。
• 查询 $[7,9]$（对应子数组 2 3 1）：
  1. 交换子数组中的位置 1 和 3（即原序列位置 7 和 9） $\rightarrow$ 1 3 2
  2. 交换子数组中的位置 2 和 3（即原序列位置 8 和 9） $\rightarrow$ 1 2 3 共 2 次交换。

【样例 2】

【样例 2 输入】

10 3
1 3 2 1 3 2 1 3 2 3
1 10
3 8
2 7

【样例 2 输出】

3
2
3

【样例 2 解释】

• 查询 $[1,10]$（对应子数组 1 3 2 1 3 2 1 3 2 3）：
  1. 交换 $a_3$ 和 $a_4 \rightarrow$ 1 3 1 2 3 2 1 3 2 3
  2. 交换 $a_2$ 和 $a_7 \rightarrow$ 1 1 1 2 3 2 3 3 2 3
  3. 交换 $a_5$ 和 $a_9 \rightarrow$ 1 1 1 2 2 2 3 3 3 3 共 3 次交换。
• 查询 $[3,8]$（对应子数组 2 1 3 2 1 3）：
  1. 交换子数组中的位置 1 和 5（即原序列位置 3 和 7） $\rightarrow$ 1 1 3 2 2 3
  2. 交换子数组中的位置 3 和 5（即原序列位置 5 和 7） $\rightarrow$ 1 1 2 2 3 3 共 2 次交换。
• 查询 $[2,7]$（对应子数组 3 2 1 3 2 1）：
  1. 交换子数组中的位置 1 和 6（即原序列位置 2 和 7） $\rightarrow$ 1 2 1 3 2 3
  2. 交换子数组中的位置 2 和 3（即原序列位置 3 和 4） $\rightarrow$ 1 1 2 3 2 3
  3. 交换子数组中的位置 4 和 5（即原序列位置 5 和 6） $\rightarrow$ 1 1 2 2 3 3 共 3 次交换。

【样例 3】

【样例 3 输入】

8 3
1 2 2 1 1 2 1 2
1 8
2 7
4 8

【样例 3 输出】

2
2
1

【样例 3 解释】

• 查询 $[1,8]$（对应子数组 1 2 2 1 1 2 1 2）：
  1. 交换 $a_2$ 和 $a_5 \rightarrow$ 1 1 2 1 2 2 1 2
  2. 交换 $a_3$ 和 $a_7 \rightarrow$ 1 1 1 1 2 2 2 2 共 2 次交换。
• 查询 $[2,7]$（对应子数组 2 2 1 1 2 1）：
  1. 交换子数组中的位置 1 和 4（即原序列位置 2 和 5） $\rightarrow$ 1 2 1 2 2 1
  2. 交换子数组中的位置 2 和 6（即原序列位置 3 和 7） $\rightarrow$ 1 1 1 2 2 2 共 2 次交换。
• 查询 $[4,8]$（对应子数组 1 1 2 1 2）：
  1. 交换子数组中的位置 3 和 4（即原序列位置 6 和 7） $\rightarrow$ 1 1 1 2 2 共 1 次交换。

【数据规模与约定】