Задача №111637. Звёздный путь

Экспедиция готовится отправиться в путь на космическом корабле нового поколения. Планируется последовательно посетить N планет звёздной системы — от планеты Земля до планеты Победа. Планеты пронумерованы от 1 до N в порядке их посещения, Земля имеет номер 1, а Победа — номер N.

Для перелёта между планетами корабль может использовать любой тип топлива, существующий в звёздной системе. Перед началом экспедиции корабль находится на планете Земля, и бак корабля пуст. Существующие типы топлива пронумерованы целыми числами, на планете с номером i можно заправиться только топливом типа ai. При посещении i-й планеты можно заправиться, полностью освободив бак от имеющегося топлива и заполнив его топливом типа ai.

На каждой планете станция заправки устроена таким образом, что в бак заправляется ровно столько топлива, сколько потребуется для перелёта до следующей планеты с топливом такого же типа. Если далее такой тип топлива не встречается, заправляться на этой планете невозможно. Иначе говоря, после заправки на i-й планете топлива хватит для посещения планет от (i + 1)-й до j-й включительно, где j — минимальный номер планеты, такой что j > i и aj = ai. Для продолжения экспедиции дальше j-й планеты корабль необходимо снова заправить на одной из этих планет.

Требуется написать программу, которая по заданным типам топлива на планетах определяет минимальное количество заправок, требуемых для экспедиции.

Входные данные

В первой строке входного файла записано число N (2 ≤ N ≤ 300 000) — количество планет.

Во второй строке входного файла записано N целых чисел a1, a2, ..., aN (1 ≤ ai ≤ 300 000) — типы топлива на планетах.

Выходные данные

В первой строке выходного файла выведите единственное число K — минимальное количество заправок, которые нужно произвести.

Во второй строке выведите K чисел, разделённых пробелами, — номера планет, на которых требуется заправиться. Номера планет требуется выводить в порядке времени заправок.

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

Примечание

Данная задача содержит три подзадачи. Для оценки каждой подзадачи используется своя группа тестов. Баллы за подзадачу начисляются только в том случае, если все тесты из этой группы успешно пройдены.

  1. Тесты из условия. Подзадача оценивается в 0 баллов.

  2. N ≤ 3000. Подзадача оценивается в 50 баллов.

  3. N ≤ 300 000. Подзадача оценивается в 50 баллов.

Примеры
Входные данные
7
1 3 2 1 3 2 3
Выходные данные
3
1 3 5
Входные данные
7
4 3 2 4 3 2 1
Выходные данные
0
Сдать: для сдачи задач необходимо войти в систему