CF2043G Problem with Queries

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.

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.

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 $ .

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