给定一个数组 $$$a$$$,由 $$$n$$$ 整数组成。您的任务是处理两种类型的 $$$q$$$ 查询:
- $$$1~p~x$$$ — 将索引 $$$p$$$ 处的元素值设置为等于 $$$x$$$;
- $$$2~l~r$$$ — 计算满足 $$$l \le i < j \le r$$$ 和 $$$a_i \ne a_j$$$ 的索引对 $$$(i, j)$$$ 的数量。
请注意,此任务中的查询是经过编码的;每个后续查询只能在计算出第二类型的先前查询的答案之后才能被解码。
输入
第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$)。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$)。
第三行包含一个整数 $$$q$$$ ($$$1 \le q \le 3 \cdot 10^5$$$) — 查询数。
接下来的 $$$q$$$ 行采用以下格式之一描述查询:
- $$$1~p'~x'$$$ ($$$0 \le p', x' \le n-1$$$);
- $$$2~l'~r'$$$ ($$$0 \le l', r' \le n-1$$$)。
查询编码如下:令 $$$\mathit{last}$$$ 为最新处理的第二类型查询的答案(最初,$$$\mathit{last} = 0$$$)。
- 如果查询的类型为 $$$1$$$,则 $$$p = ((p' + \mathit{last}) \bmod n) + 1$$$,$$$x = ((x' + \mathit{last}) \bmod n) + 1$$$。
- 如果查询的类型为 $$$2$$$,则 $$$l = ((l' + \mathit{last}) \bmod n) + 1$$$,$$$r = ((r' + \mathit{last}) \bmod n) + 1$$$。如果 $$$l > r$$$,则交换它们的值。
在回答第二类型的每个查询后,不要忘记更新 $$$\mathit{last}$$$ 的值。
对输入的附加约束:至少有一个第二类型的查询。
输出
对于第二种类型的每个查询,打印答案 - 索引对 $$$(i, j)$$$ 的数量,使得 $$$l \le i < j \le r$$$ 和 $$$a_i \ne a_j$$$。
示例
输入 #1
3 1 2 3 5 2 0 2 1 0 2 2 0 2 1 2 0 2 1 0
输出 #1
3 2 0
输入 #2
7 1 3 4 4 7 1 3 3 2 1 6 2 1 0 2 5 6
输出 #2
13 18 0
注意
在第一个示例中,实际查询(解码后)是:
- 2 1 3
- 1 1 3
- 2 1 3
- 1 2 3
- 2 1 3