题目描述

33DAI 拿到了一个长度为 $n$ 的序列 $a_1\sim a_n$。

他有 $Q$ 个问题，第 $i$ 个问题会给你一个区间 $[l_i,r_i]$，你需要告诉他这个区间有多少个不同的数。

输入格式

第一行两个数 $n,Q$。

第二行为空格隔开的 $n$ 个数 $a_1\sim a_n$。

接下来 $Q$ 行，每行为空格隔开的两个数 $x,y$，可以通过 $x,y$ 算出第 $i$ 个询问 $[l_i,r_i]$，计算方法如下：

分别计算

• $xx = ((x\times ans_{i-1}) \bmod n) + 1$
• $yy = ((y\times ans_{i-1}) \bmod n) + 1$

其中 $ans_i$ 表示第 $i$ 个问题的答案，$ans_0 = 1$。

则第 $i$ 个问题的 $l_i,r_i$ 分别为：

• $l_i = \min(xx,yy)$
• $r_i = \max(xx,yy)$

输出格式

输出 $Q$ 行，第 $i$ 行为第 $i$ 个问题的答案。

10 3
1 2 3 4 5 1 2 3 4 5
9 10
1 5
3 6

5
1
4

• 对于 $x=9,y=10,ans_{i-1}=1$ 计算出：$xx=9\times 1\bmod 10+1 = 10, yy = 10\times 1 \bmod 10 +1 = 1$
  • 第一个问题为 $[1,10]$，$ans_1=5$。
• 对于 $x=1,y=5,ans_{i-1}=5$ 计算出：$xx=1\times 5\bmod 10+1 = 6, yy = 5\times 5 \bmod 10 +1 = 6$
  • 第二个问题为 $[6,6]$，$ans_2=1$。
• 对于 $x=3,y=6,ans_{i-1}=1$ 计算出：$xx=3\times 1\bmod 10+1 = 4, yy = 6\times 1 \bmod 10 +1 = 7$
  • 第三个问题为 $[4,7]$，$ans_3=4$。

数据规模与约定

对于 $100\%$ 的数据，$1 \le n \le 10^5$，$1\le Q\le 100$，$1\le a_i\le 10^9$。

• 子任务 1（30 分）：保证所有 $a_i$ 各不相同。
• 子任务 2（30 分）：保证 $n\le 100$。
• 子任务 3（40 分）：没有特殊限制。