G. Problem with Queriestime limit per test8 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard outputYou 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.InputThe 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.OutputFor 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$$$.ExamplesInput31 2 352 0 21 0 22 0 21 2 02 1 0Output3 2 0 Input71 3 4 4 7 1 332 1 62 1 02 5 6Output13 18 0 NoteIn the first example, the actual queries (after decoding) are: 2 1 3 1 1 3 2 1 3 1 2 3 2 1 3