Задача A. Звёздный путь (ROI-2013)

Автор:Жюри ROI-2013   Ограничение времени:3 сек
Входной файл:expedition.in   Ограничение памяти:256 Мб
Выходной файл:expedition.out  

Условие

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

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

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

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

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

В первой строке входного файла записано число N — количество планет.

Во второй строке входного файла записано N целых чисел a1, a2, …, aN — типы топлива на планетах.

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

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

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

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

Ограничения

2 ≤ N ≤ 300 000;

1 ≤ ai ≤ 300 000;

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

Входной файл (expedition.in) Выходной файл (expedition.out)
1
7
1 3 2 1 3 2 3
3
1 3 5
2
7
4 3 2 4 3 2 1
0

0.077s 0.017s 13