В задаче требуется для $$$q$$$ запросов понять, существует ли $$$t \in [1, k]$$$, такое что $$$Set([l, r]) = Set([t, k])$$$, где $$$Set([l, r])$$$ — множество чисел $$$a_i$$$, где $$$l \le i \le r$$$. Также, если $$$t$$$ существует, то найти максимальную сумму затемнённостей комнат на $$$[t, k]$$$ для всех подходящих $$$t$$$.

Заметим, что все подходящие для нас $$$t$$$, если таковые существуют, будут лежать на одном отрезке. Это следует из того, что чем левее двигается граница $$$t$$$, тем сильнее размер $$$Set([t, k])$$$ может увеличиться, а мы хотим, чтобы множества, а значит, и их размеры, совпали.

Найдём максимальный и минимальный суффикс отрезка $$$[1, k]$$$ с $$$p$$$ различными числами, где $$$p$$$ — количество различных на отрезке $$$[l, r]$$$. Найти количество различных на отрезке $$$[l, r]$$$ — это базовая задача на персистентное дерево отрезков, но так как запросы даны в оффлайне, это можно сделать и обычным деревом отрезков, или даже деревом Фенвика. Отсортируем запросы по $$$r$$$ и пройдём по массиву слева направо. При этом будем поддерживать для каждого $$$x$$$ последнее найденное вхождение $$$x$$$, то есть наибольшее $$$i$$$, что $$$a_i = x$$$. Для каждого такого $$$i$$$, что $$$i$$$ — последнее вхождение какого-либо числа, прибавим 1 к $$$i$$$-му элементу дерева Фенвика. Пусть мы прошли по первым $$$k$$$ элементам массива. Рассмотрим все такие $$$[l, r]$$$, что $$$r = k$$$, и возьмём сумму на отрезке $$$[l, r]$$$ в дереве Фенвика. Она и будет равна количеству различных на отрезке $$$[l, r]$$$.

Далее найдём $$$t_1$$$, $$$t_2$$$ такие, что на $$$[t_2, k]$$$ — $$$p$$$ различных, а на $$$[t_1, k]$$$ — $$$p+1$$$ различных. Для этого ещё раз пройдёмся по массиву, как в предыдущей части, и используем спуск по персистентному ДО или Фенвику. Тогда только $$$t \in (t_1, t_2]$$$ могут нам подойти. Мы смогли проверить на совпадения количества различных, осталось проверить, что сами множества совпадают. Для этого будем хранить какую-нибудь хеш-функцию на различных элементах, поддерживая это в персистентном дереве отрезков или в дереве Фенвика. Например, можно каждой игре сопоставить случайное число до $$$10^{18}$$$ и суммировать их, или ксорить их.

Теперь, если хеш и количество различных совпадают, то любое $$$t \in (t_1, t_2]$$$ удовлетворяет требованиям Стефани, осталось только максимизировать сумму на $$$[t, k]$$$. Её можно посчитать через разность двух суффиксных, тогда нам надо будет на $$$(t_1, t_2]$$$ находить наибольшую суффиксную сумму. Это можно сделать, использовав либо sparse table, либо обычное дерево отрезков.