G. Задача на запросы
ограничение по времени на тест
8 секунд
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Дан массив $$$a$$$, состоящий из $$$n$$$ целых чисел. Вам нужно обработать $$$q$$$ запросов двух типов:

  • $$$1~p~x$$$ — присвоить элементу массива на позиции $$$p$$$ значение $$$x$$$;
  • $$$2~l~r$$$ — подсчитать количество пар позиций $$$(i, j)$$$, где $$$l \le i < j \le r$$$ и $$$a_i \ne a_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$$$.

Примеры
Входные данные
3
1 2 3
5
2 0 2
1 0 2
2 0 2
1 2 0
2 1 0
Выходные данные
3 2 0
Входные данные
7
1 3 4 4 7 1 3
3
2 1 6
2 1 0
2 5 6
Выходные данные
13 18 0
Примечание

В первом примере реальные запросы (после декодирования) такие:

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