Эта задача такая же как и предыдущая, но с большими ограничениями.
Широ только что переехала в новый дом. Она хочет позвать друзей в гости, чтобы поиграть в монополию. Однако её дом достаточно мал, так что она может позвать в гости не более одного друга за раз.
В каждый из \(n\) дней, начиная с дня, в который Широ переехала в новый дом, к ней будет в гости ровно одна кошка. Кошка приходящая в \(i\)-й день носит ленточку цвета \(u_i\). Широ хочет узнать наибольшее число \(x\), такое что если рассмотреть префикс из первых \(x\) дней, то можно убрать ровно один день из них, что каждый цвет ленточек, который встречался среди оставшихся \(x - 1\) дней встречается одинаковое число раз.
Например, рассмотрим следующую последовательность \(u_i\): \([2, 2, 1, 1, 5, 4, 4, 5]\). Тогда \(x = 7\) образует подходящий префикс, так как если удалить самый левый день с \(u_i = 5\), то получится что среди оставшихся \(x - 1\) дней каждый цвет встречается два раза. Обратите внимание, что \(x = 8\) не образует подходящий префикс, так как нужно убрать ровно один день.
Так как Широ всего лишь кошка, она не очень хороша в подсчётах и ей нужна ваша помощь с вычислением наибольшего подходящего префикса.
Примечание
В первом примере можно рассмотреть префикс из \(13\) дней, так как если убрать последний день из этого префиса, то все оставшиеся цвета \(1\), \(2\), \(3\), и \(4\) будут встречаться одинаковое число раз (\(3\) раза). Обратите внимание, что подходит также префикс из \(10\) дней (нужно удалить \(10\)-й день), однако требуется найти наибольший подходящий префикс.
В четвёртом примере, если рассмотреть префикс из первых \(6\) дней, то можно убрать третий день, тогда останутся цвета \(1\), \(2\), \(3\), \(4\) и \(5\), встречающиеся по одному разу.