G. Problem with Queries
time limit per test
8 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given an array $$$a$$$, consisting of $$$n$$$ integers. Your task is to process $$$q$$$ queries of two types:

  • $$$1~p~x$$$ — set the value of the element at index $$$p$$$ equal to $$$x$$$;
  • $$$2~l~r$$$ — count the number of pairs of indices $$$(i, j)$$$ such that $$$l \le i < j \le r$$$ and $$$a_i \ne a_j$$$.

Note that the queries in this task are encoded; each subsequent query can only be decoded after calculating the answer to the preceding query of the second type.

Input

The first line contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$).

The third line contains a single integer $$$q$$$ ($$$1 \le q \le 3 \cdot 10^5$$$) — the number of queries.

The next $$$q$$$ lines describe the queries in one of the following formats:

  • $$$1~p'~x'$$$ ($$$0 \le p', x' \le n-1$$$);
  • $$$2~l'~r'$$$ ($$$0 \le l', r' \le n-1$$$).

The queries are encoded as follows: let $$$\mathit{last}$$$ be the answer to the latest processed query of the second type (initially, $$$\mathit{last} = 0$$$).

  • if the type of the query is $$$1$$$, then $$$p = ((p' + \mathit{last}) \bmod n) + 1$$$, $$$x = ((x' + \mathit{last}) \bmod n) + 1$$$.
  • if the type of the query is $$$2$$$, $$$l = ((l' + \mathit{last}) \bmod n) + 1$$$, $$$r = ((r' + \mathit{last}) \bmod n) + 1$$$. If $$$l > r$$$, swap their values.

Don't forget to update the value of $$$\mathit{last}$$$ after answering each query of the second type.

Additional constraint on the input: there is at least one query of the second type.

Output

For each query of the second type, print the answer — the number of pairs of indices $$$(i, j)$$$ such that $$$l \le i < j \le r$$$ and $$$a_i \ne a_j$$$.

Examples
Input
3
1 2 3
5
2 0 2
1 0 2
2 0 2
1 2 0
2 1 0
Output
3 2 0
Input
7
1 3 4 4 7 1 3
3
2 1 6
2 1 0
2 5 6
Output
13 18 0
Note

In the first example, the actual queries (after decoding) are:

  • 2 1 3
  • 1 1 3
  • 2 1 3
  • 1 2 3
  • 2 1 3