Дан массив \(a\), состоящий из \(n\) целых чисел. Вам нужно обработать \(q\) запросов двух типов:
Обратите внимание, что запросы в этой задаче закодированы; каждый следующий запрос вы сможете раскодировать, вычислив ответ на предшествующий ему запрос второго типа.
Первая строка входных данных содержит одно целое число \(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\) строк описывает запрос в одном из следующих форматов:
Запросы закодированы следующим образом: пусть \(\mathit{last}\) будет ответом на последний уже обработанный запрос второго типа (изначально \(\mathit{last} = 0\)).
Не забудьте обновить значение \(\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
8000 ms 1024 Mb Правила оформления программ и список ошибок при автоматической проверке задач