Задача C2. Сумма не без разнообразия

Входной файл:input.txt   Ограничение времени:2 сек
Выходной файл:output.txt   Ограничение памяти:256 Мб

Условие

Задана последовательность целых чисел A1, A2, …, AN. Необходимо выбрать из нее подпоследовательность из подряд стоящих чисел Ai, Ai + 1, …, Aj так, чтобы она содержала не менее K различных чисел, и сумма S = Ai + Ai + 1 + …  + Aj была максимальной.

Формат входного файла

Первая строка ввода содержит целые числа N и K (1 ≤ K ≤ N ≤ 200 000). Вторая строка содержит N целых чисел A1, A2, …, AN (Ai≤ 1 000 000 000).

Формат выходного файла

В первой строке необходимо вывести максимальное возможное значение суммы S. Во второй строке выведите индексы первого и последнего элементов найденной оптимальной подпоследовательности. Если существует несколько решений, подойдет любое из них. Если не существует подпоследовательностей, удовлетворяющих решению задачи, выведите одну строку со словом IMPOSSIBLE.

Ограничения

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
7 3
-99 1 2 -100 3 2 3
-89
2 7
2
3 2
1 1 1
IMPOSSIBLE

0.099s 0.021s 15